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

17
package 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

17
import 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

17
import 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







© 2021, kalkicode.com, All rights reserved