Calculate cost of visiting all array elements in increasing order
Given an array of integer elements. Our goal is to find the visiting cost in each element in array. visiting cost is calculated by sum of index in minimum element to next minimum element. For example.
Input : arr[] = {6 , 2 , 5 , -1 , 3 , 7}
Output : 17
/*
First cost to find min element
[6, 2, 5, -1, 3, 7 ]
⇡ cost 3
[position of element]
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [3 - 1] = 2
cost = 2 + cost
cost = 5
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 1] = 3
cost = 3 + cost
cost = 8
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 2] = 2
cost = 2 + cost
cost = 10
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [2 - 0] = 2
cost = 2 + cost
cost = 12
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [5 - 0] = 5
cost = 5 + cost
cost = 17
-----------------------------------
Result : 17
*/
We assume given array contains distinct elements. Because we visit first smallest element to next small element. Here given code implementation process.
import java.util.HashMap;
// Java Program
// Calculate cost of visiting all array elements in increasing order
public class Cost
{
public int absValue(int x)
{
if (x < 0)
{
return -x;
}
return x;
}
public void findCost(int[] arr, int n)
{
HashMap < Integer, Integer > record =
new HashMap < Integer, Integer > ();
int result = 0;
int back = -1;
for (int i = 0; i < n; ++i)
{
if (!record.containsKey(arr[i]))
{
// Collect position by value
record.put(arr[i], i);
}
}
// Calculate jumping cost from min to next minimum
for (int info: record.keySet())
{
if (back == -1)
{
// First min position
back = record.get(info);
// Add first cost
result += back;
}
else
{
// Add jumping cost
result += absValue(back - record.get(info));
back = record.get(info);
}
}
System.out.println(result);
}
public static void main(String args[])
{
Cost task = new Cost();
// Array of distinct integer elements
int[] arr = {
6 , 2 , 5 , -1 , 3 , 7
};
int n = arr.length;
/*
arr [] = [6, 2, 5, -1, 3, 7 ]
First cost to find min element
[6, 2, 5, -1, 3, 7 ]
⇡ cost 3
[position of element]
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [3 - 1] = 2
cost = 2 + cost
cost = 5
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 1] = 3
cost = 3 + cost
cost = 8
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 2] = 2
cost = 2 + cost
cost = 10
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [2 - 0] = 2
cost = 2 + cost
cost = 12
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [5 - 0] = 5
cost = 5 + cost
cost = 17
-----------------------------------
Result : 17
*/
task.findCost(arr, n);
}
}Output
17// Include header file
#include <iostream>
#include <map>
using namespace std;
// C++ Program
// Calculate cost of visiting all array elements in increasing order
class Cost
{
public: int absValue(int x)
{
if (x < 0)
{
return -x;
}
return x;
}
void findCost(int arr[], int n)
{
// Sorted map
map < int, int > record;
int result = 0;
int back = -1;
for (int i = 0; i < n; ++i)
{
if (record.find(arr[i]) == record.end())
{
// Collect position by value
record[arr[i]] = i;
}
}
// Calculate jumping cost from min to next minimum
for (auto &info: record)
{
if (back == -1)
{
// First min position
back = info.second;
// Add first cost
result += back;
}
else
{
// Add jumping cost
result += (this->absValue(back - info.second));
back = info.second;
}
}
cout << result << endl;
}
};
int main()
{
Cost *task = new Cost();
// Array of distinct integer elements
int arr[] = {
6 , 2 , 5 , -1 , 3 , 7
};
int n = sizeof(arr) / sizeof(arr[0]);
/*
arr [] = [6, 2, 5, -1, 3, 7 ]
First cost to find min element
[6, 2, 5, -1, 3, 7 ]
⇡ cost 3
[position of element]
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [3 - 1] = 2
cost = 2 + cost
cost = 5
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 1] = 3
cost = 3 + cost
cost = 8
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 2] = 2
cost = 2 + cost
cost = 10
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [2 - 0] = 2
cost = 2 + cost
cost = 12
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [5 - 0] = 5
cost = 5 + cost
cost = 17
-----------------------------------
Result : 17
*/
task->findCost(arr, n);
return 0;
}Output
17// Include namespace system
using System;
using System.Collections.Generic;
// Csharp Program
// Calculate cost of visiting all array elements in increasing order
public class Cost
{
public int absValue(int x)
{
if (x < 0)
{
return -x;
}
return x;
}
public void findCost(int[] arr, int n)
{
SortedDictionary < int, int > record =
new SortedDictionary < int, int > ();
int result = 0;
int back = -1;
for (int i = 0; i < n; ++i)
{
if (!record.ContainsKey(arr[i]))
{
// Collect position by value
record.Add(arr[i], i);
}
}
// Calculate jumping cost from min to next minimum
foreach(KeyValuePair < int, int > info in record)
{
if (back == -1)
{
// First min position
back = info.Value;
// Add first cost
result += back;
}
else
{
// Add jumping cost
result += this.absValue(back - info.Value);
back = info.Value;
}
}
Console.WriteLine(result);
}
public static void Main(String[] args)
{
Cost task = new Cost();
// Array of distinct integer elements
int[] arr = {
6 , 2 , 5 , -1 , 3 , 7
};
int n = arr.Length;
/*
arr [] = [6, 2, 5, -1, 3, 7 ]
First cost to find min element
[6, 2, 5, -1, 3, 7 ]
⇡ cost 3
[position of element]
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [3 - 1] = 2
cost = 2 + cost
cost = 5
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 1] = 3
cost = 3 + cost
cost = 8
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 2] = 2
cost = 2 + cost
cost = 10
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [2 - 0] = 2
cost = 2 + cost
cost = 12
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [5 - 0] = 5
cost = 5 + cost
cost = 17
-----------------------------------
Result : 17
*/
task.findCost(arr, n);
}
}Output
17package main
import (
"fmt"
"sort"
)
// Go Program
// Calculate cost of visiting all array elements in increasing order
type Cost struct {}
func getCost() * Cost {
var me *Cost = &Cost {}
return me
}
func(this Cost) absValue(x int) int {
if x < 0 {
return -x
}
return x
}
func(this Cost) findCost(arr[] int, n int) {
var record = make(map[int] int)
var result int = 0
var back int = -1
for i := 0 ; i < n ; i++ {
if _, found := record[arr[i]] ; !found {
// Collect position by value
record[arr[i]] = i
}
}
keys := make([]int, len(record))
i := 0
// Collect key
for k, _ := range record {
keys[i] = k
i+=1
}
// Sort key
sort.Ints(keys)
// Calculate jumping cost from min to next minimum
for _, v := range keys {
if back == -1 {
// First min position
back = record[v]
// Add first cost
result += back
} else {
// Add jumping cost
result += this.absValue(back - record[v])
back = record[v]
}
}
fmt.Println(result)
}
func main() {
var task * Cost = getCost()
// Array of distinct integer elements
var arr = [] int {
6,
2,
5,
-1,
3,
7,
}
var n int = len(arr)
/*
arr [] = [6, 2, 5, -1, 3, 7 ]
First cost to find min element
[6, 2, 5, -1, 3, 7 ]
⇡ cost 3
[position of element]
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [3 - 1] = 2
cost = 2 + cost
cost = 5
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 1] = 3
cost = 3 + cost
cost = 8
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 2] = 2
cost = 2 + cost
cost = 10
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [2 - 0] = 2
cost = 2 + cost
cost = 12
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [5 - 0] = 5
cost = 5 + cost
cost = 17
-----------------------------------
Result : 17
*/
task.findCost(arr, n)
}Output
17<?php
// Php Program
// Calculate cost of visiting all array elements in increasing order
class Cost
{
public function absValue($x)
{
if ($x < 0)
{
return -$x;
}
return $x;
}
public function findCost($arr, $n)
{
$record = array();
$result = 0;
$back = -1;
for ($i = 0; $i < $n; ++$i)
{
if (!array_key_exists($arr[$i], $record))
{
// Collect position by value
$record[$arr[$i]] = $i;
}
}
ksort($record);
// Calculate jumping cost from min to next minimum
foreach($record as $key => $value)
{
if ($back == -1)
{
// First min position
$back = $value;
// Add first cost
$result += $back;
}
else
{
// Add jumping cost
$result += $this->absValue($back - $value);
$back = $value;
}
}
echo($result.
"\n");
}
}
function main()
{
$task = new Cost();
// Array of distinct integer elements
$arr = array(6, 2, 5, -1, 3, 7);
$n = count($arr);
/*
arr [] = [6, 2, 5, -1, 3, 7 ]
First cost to find min element
[6, 2, 5, -1, 3, 7 ]
⇡ cost 3
[position of element]
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [3 - 1] = 2
cost = 2 + cost
cost = 5
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 1] = 3
cost = 3 + cost
cost = 8
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 2] = 2
cost = 2 + cost
cost = 10
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [2 - 0] = 2
cost = 2 + cost
cost = 12
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [5 - 0] = 5
cost = 5 + cost
cost = 17
-----------------------------------
Result : 17
*/
$task->findCost($arr, $n);
}
main();Output
17// Node JS Program
// Calculate cost of visiting all array elements in increasing order
class Cost
{
absValue(x)
{
if (x < 0)
{
return -x;
}
return x;
}
findCost(arr, n)
{
var record = new Map();
var result = 0;
var back = -1;
for (var i = 0; i < n; ++i)
{
if (!record.has(arr[i]))
{
// Collect position by value
record.set(arr[i], i);
}
}
var v = new Map([...record.entries()].sort());
// Calculate jumping cost from min to next minimum
for (let [key, value] of v)
{
if (back == -1)
{
// First min position
back = value;
// Add first cost
result += back;
}
else
{
// Add jumping cost
result += this.absValue(back - value);
back = value;
}
}
console.log(result);
}
}
function main()
{
var task = new Cost();
// Array of distinct integer elements
var arr = [6, 2, 5, -1, 3, 7];
var n = arr.length;
/*
arr [] = [6, 2, 5, -1, 3, 7 ]
First cost to find min element
[6, 2, 5, -1, 3, 7 ]
⇡ cost 3
[position of element]
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [3 - 1] = 2
cost = 2 + cost
cost = 5
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 1] = 3
cost = 3 + cost
cost = 8
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 2] = 2
cost = 2 + cost
cost = 10
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [2 - 0] = 2
cost = 2 + cost
cost = 12
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [5 - 0] = 5
cost = 5 + cost
cost = 17
-----------------------------------
Result : 17
*/
task.findCost(arr, n);
}
main();Output
17import collections
# Python 3 Program
# Calculate cost of visiting all array elements in increasing order
class Cost :
def absValue(self, x) :
if (x < 0) :
return -x
return x
def findCost(self, arr, n) :
record = dict()
result = 0
back = -1
i = 0
while (i < n) :
if (not(arr[i] in record.keys())) :
# Collect position by value
record[arr[i]] = i
i += 1
v = collections.OrderedDict(sorted(record.items()))
for key, value in v.items() :
if (back == -1) :
# First min position
back = value
# Add first cost
result += back
else :
# Add jumping cost
result += self.absValue(back - value)
back = value
print(result)
def main() :
task = Cost()
# Array of distinct integer elements
arr = [6, 2, 5, -1, 3, 7]
n = len(arr)
# arr [] = [6, 2, 5, -1, 3, 7 ]
# First cost to find min element
# [6, 2, 5, -1, 3, 7 ]
# ⇡ cost 3
# [position of element]
# Find next smallest
# [6, 2, 5, -1, 3, 7 ]
# ⇡ ⇡ position [3 - 1] = 2
# cost = 2 + cost
# cost = 5
# Find next smallest
# [6, 2, 5, -1, 3, 7 ]
# ⇡ ⇡ position [4 - 1] = 3
# cost = 3 + cost
# cost = 8
# Find next smallest
# [6, 2, 5, -1, 3, 7 ]
# ⇡ ⇡ position [4 - 2] = 2
# cost = 2 + cost
# cost = 10
# Find next smallest
# [6, 2, 5, -1, 3, 7 ]
# ⇡ ⇡ position [2 - 0] = 2
# cost = 2 + cost
# cost = 12
# Find next smallest
# [6, 2, 5, -1, 3, 7 ]
# ⇡ ⇡ position [5 - 0] = 5
# cost = 5 + cost
# cost = 17
# -----------------------------------
# Result : 17
task.findCost(arr, n)
if __name__ == "__main__": main()Output
17# Ruby Program
# Calculate cost of visiting all array elements in increasing order
class Cost
def absValue(x)
if (x < 0)
return -x
end
return x
end
def findCost(arr, n)
record = Hash.new()
result = 0
back = -1
i = 0
while (i < n)
if (!record.key?(arr[i]))
# Collect position by value
record[arr[i]] = i
end
i += 1
end
# Sort hash by key
record = record.sort.to_h
# Calculate jumping cost from min to next minimum
record.each { | key, value |
if (back == -1)
# First min position
back = value
# Add first cost
result += back
else
# Add jumping cost
result += self.absValue(back - value)
back = value
end
}
print(result, "\n")
end
end
def main()
task = Cost.new()
# Array of distinct integer elements
arr = [6, 2, 5, -1, 3, 7]
n = arr.length
# arr [] = [6, 2, 5, -1, 3, 7 ]
# First cost to find min element
# [6, 2, 5, -1, 3, 7 ]
# ⇡ cost 3
# [position of element]
# Find next smallest
# [6, 2, 5, -1, 3, 7 ]
# ⇡ ⇡ position [3 - 1] = 2
# cost = 2 + cost
# cost = 5
# Find next smallest
# [6, 2, 5, -1, 3, 7 ]
# ⇡ ⇡ position [4 - 1] = 3
# cost = 3 + cost
# cost = 8
# Find next smallest
# [6, 2, 5, -1, 3, 7 ]
# ⇡ ⇡ position [4 - 2] = 2
# cost = 2 + cost
# cost = 10
# Find next smallest
# [6, 2, 5, -1, 3, 7 ]
# ⇡ ⇡ position [2 - 0] = 2
# cost = 2 + cost
# cost = 12
# Find next smallest
# [6, 2, 5, -1, 3, 7 ]
# ⇡ ⇡ position [5 - 0] = 5
# cost = 5 + cost
# cost = 17
# -----------------------------------
# Result : 17
task.findCost(arr, n)
end
main()Output
17
import scala.collection.mutable._;
// Scala Program
// Calculate cost of visiting all array elements in increasing order
class Cost()
{
def absValue(x: Int): Int = {
if (x < 0)
{
return -x;
}
return x;
}
def findCost(arr: Array[Int], n: Int): Unit = {
var record: HashMap[Int, Int] = new HashMap[Int, Int]();
var result: Int = 0;
var back: Int = -1;
var i: Int = 0;
while (i < n)
{
if (!record.contains(arr(i)))
{
// Collect position by value
record.addOne(arr(i), i);
}
i += 1;
}
// Calculate jumping cost from min to next minimum
for ((key, value) <- record)
{
if (back == -1)
{
// First min position
back = value;
// Add first cost
result += back;
}
else
{
// Add jumping cost
result += absValue(back - record.get(key).get);
back = value;
}
}
println(result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Cost = new Cost();
// Array of distinct integer elements
var arr: Array[Int] = Array(6, 2, 5, -1, 3, 7);
var n: Int = arr.length;
/*
arr [] = [6, 2, 5, -1, 3, 7 ]
First cost to find min element
[6, 2, 5, -1, 3, 7 ]
⇡ cost 3
[position of element]
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [3 - 1] = 2
cost = 2 + cost
cost = 5
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 1] = 3
cost = 3 + cost
cost = 8
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 2] = 2
cost = 2 + cost
cost = 10
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [2 - 0] = 2
cost = 2 + cost
cost = 12
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [5 - 0] = 5
cost = 5 + cost
cost = 17
-----------------------------------
Result : 17
*/
task.findCost(arr, n);
}
}Output
17import Foundation;
// Swift 4 Program
// Calculate cost of visiting all array elements in increasing order
class Cost
{
func absValue(_ x: Int) -> Int
{
if (x < 0)
{
return -x;
}
return x;
}
func findCost(_ arr: [Int], _ n: Int)
{
var record = [Int : Int]();
var result: Int = 0;
var back: Int = -1;
var i: Int = 0;
while (i < n)
{
if (!record.keys.contains(arr[i]))
{
// Collect position by value
record[arr[i]] = i;
}
i += 1;
}
let info = Array(record.keys).sorted();
// Calculate jumping cost from min to next minimum
for key in info
{
if (back == -1)
{
// First min position
back = record[key]!;
// Add first cost
result += back;
}
else
{
// Add jumping cost
result += self.absValue(back - record[key]!);
back = record[key]!;
}
}
print(result);
}
}
func main()
{
let task: Cost = Cost();
// Array of distinct integer elements
let arr: [Int] = [6, 2, 5, -1, 3, 7];
let n: Int = arr.count;
/*
arr [] = [6, 2, 5, -1, 3, 7 ]
First cost to find min element
[6, 2, 5, -1, 3, 7 ]
⇡ cost 3
[position of element]
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [3 - 1] = 2
cost = 2 + cost
cost = 5
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 1] = 3
cost = 3 + cost
cost = 8
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 2] = 2
cost = 2 + cost
cost = 10
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [2 - 0] = 2
cost = 2 + cost
cost = 12
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [5 - 0] = 5
cost = 5 + cost
cost = 17
-----------------------------------
Result : 17
*/
task.findCost(arr, n);
}
main();Output
17// Kotlin Program
// Calculate cost of visiting all array elements in increasing order
class Cost
{
fun absValue(x: Int): Int
{
if (x < 0)
{
return -x;
}
return x;
}
fun findCost(arr: Array < Int > , n: Int): Unit
{
val record: HashMap < Int, Int > = HashMap < Int, Int > ();
var result: Int = 0;
var back: Int = -1;
var i: Int = 0;
while (i < n)
{
if (!record.containsKey(arr[i]))
{
// Collect position by value
record.put(arr[i], i);
}
i += 1;
}
// Calculate jumping cost from min to next minimum
for ((key, value) in record)
{
if (back == -1)
{
// First min position
back = value;
// Add first cost
result += back;
}
else
{
// Add jumping cost
result += this.absValue(back - record.getValue(key));
back = value;
}
}
println(result);
}
}
fun main(args: Array < String > ): Unit
{
val task: Cost = Cost();
// Array of distinct integer elements
val arr: Array < Int > = arrayOf(6, 2, 5, -1, 3, 7);
val n: Int = arr.count();
/*
arr [] = [6, 2, 5, -1, 3, 7 ]
First cost to find min element
[6, 2, 5, -1, 3, 7 ]
⇡ cost 3
[position of element]
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [3 - 1] = 2
cost = 2 + cost
cost = 5
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 1] = 3
cost = 3 + cost
cost = 8
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [4 - 2] = 2
cost = 2 + cost
cost = 10
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [2 - 0] = 2
cost = 2 + cost
cost = 12
Find next smallest
[6, 2, 5, -1, 3, 7 ]
⇡ ⇡ position [5 - 0] = 5
cost = 5 + cost
cost = 17
-----------------------------------
Result : 17
*/
task.findCost(arr, n);
}Output
17
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment