Given an array arr[] consisting of N integers, the task is to find the total cost of visiting all the array elements in ascending order, starting from 0, if the cost of a move from index i to the index j is the absolute difference between i and j.
Examples:
Input: arr[ ] = { 4, 3, 2, 5, 1 }
Output: 11
Explanation:
Jump from index 0 to index 4. Cost = abs(4 – 0) = 4.
Jump from index 4 to index 2. Cost = abs(4 – 2) = 2.
Jump from index 2 to index1. Cost = abs(2 – 1) = 1.
Jump from index 1 to index 0. Cost = abs(1 – 0) = 1.
Jump from index 0 to index 3. Cost = abs(0 – 3) = 3.
Therefore, the total cost of visiting all array elements in ascending order = (4 + 2 + 1 + 1 + 3 = 11).Input: arr[ ] = { 1, 2, 3 }
Output: 2
Approach: The idea is to use the concept of sorting of the vector of pairs. Follow the steps below to solve the problem:
- Initialize a pair of vector<pair<int, int> >, say v, to store the pairs of elements and their respective positions.
- Traverse the array arr[] and push the pair {arr[i], i} in the vector v.
- Initialize two variables, say ans = 0 and last = 0, to store the total cost required and the index of the last visited element.
- Sort the vector of pairs in ascending order.
- Traverse the vector v and increment ans by abs(v[i].second – last). Update last as last = arr[i].second.
- After completing the above steps, print the answer obtained as ans.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate total// cost of visiting array// elements in increasing orderint calculateDistance(int arr[], int N){ // Stores the pair of element // and their positions vector<pair<int, int> > v; // Traverse the array arr[] for (int i = 0; i < N; i++) // Push the pair {arr[i], i} in v v.push_back({ arr[i], i }); // Sort the vector in ascending order. sort(v.begin(), v.end()); // Stores the total cost int ans = 0; // Stores the index of last element visited int last = 0; // Traverse the vector v for (auto j : v) { // Increment ans ans += abs(j.second - last); // Assign last = j.second; } // Return ans return ans;}// Driver Codeint main(){ int arr[] = { 4, 3, 2, 5, 1 }; int N = sizeof(arr) / sizeof(arr[0]); cout << calculateDistance(arr, N);} |
Java
// java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Pair class static class Pair { int first; int second; Pair(int first, int second) { this.first = first; this.second = second; } } // Function to calculate total // cost of visiting array // elements in increasing order static int calculateDistance(int arr[], int N) { // Stores the pair of element // and their positions Pair v[] = new Pair[N]; // Traverse the array arr[] for (int i = 0; i < N; i++) // Push the pair {arr[i], i} in v v[i] = new Pair(arr[i], i); // Sort the vector in ascending order. Arrays.sort(v, (p1, p2) -> { if (p1.first != p2.first) return p1.first - p2.first; return p1.second - p2.second; }); // Stores the total cost int ans = 0; // Stores the index of last element visited int last = 0; // Traverse the vector v for (Pair j : v) { // Increment ans ans += Math.abs(j.second - last); // Assign last = j.second; } // Return ans return ans; } // Driver Code public static void main(String[] args) { int arr[] = { 4, 3, 2, 5, 1 }; int N = arr.length; // Function call System.out.println(calculateDistance(arr, N)); }}// This code is contributed by Kingash. |
Python3
# Python3 implementation of the above approach# Function to calculate total# cost of visiting array# elements in increasing orderdef calculateDistance(arr, N): # Stores the pair of element # and their positions v = [] # Traverse the array arr[] for i in range(N): # Push the pair {arr[i], i} in v v.append([arr[i], i]) # Sort the vector in ascending order. v.sort() # Stores the total cost ans = 0 # Stores the index of last element visited last = 0 # Traverse the vector v for j in v: # Increment ans ans += abs(j[1] - last) # Assign last = j[1] # Return ans return ans# Driver Codeif __name__ == "__main__" : arr = [ 4, 3, 2, 5, 1 ] N = len(arr) print(calculateDistance(arr, N)) # This code is contributed by AnkThon |
C#
using System;using System.Linq;namespace GFG{ class Program { // Pair class class Pair { public int first; public int second; public Pair(int first, int second) { this.first = first; this.second = second; } } // Function to calculate total // cost of visiting array // elements in increasing order static int CalculateDistance(int[] arr, int N) { // Stores the pair of element // and their positions Pair[] v = new Pair[N]; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Push the pair {arr[i], i} in v v[i] = new Pair(arr[i], i); } // Sort the vector in ascending order. Array.Sort(v, (p1, p2) => { if (p1.first != p2.first) { return p1.first - p2.first; } return p1.second - p2.second; }); // Stores the total cost int ans = 0; // Stores the index of last element visited int last = 0; // Traverse the vector v foreach (Pair j in v) { // Increment ans ans += Math.Abs(j.second - last); // Assign last = j.second; } // Return ans return ans; } // Driver Code static void Main(string[] args) { int[] arr = { 4, 3, 2, 5, 1 }; int N = arr.Length; // Function call Console.WriteLine(CalculateDistance(arr, N)); } }}// This code is contributed by phasing17. |
Javascript
<script>// Javascript implementation of the above approach// Function to calculate total// cost of visiting array// elements in increasing orderfunction calculateDistance(arr, N){ // Stores the pair of element // and their positions var v = []; // Traverse the array arr[] for (var i = 0; i < N; i++) { // Push the pair {arr[i], i} in v v.push([ arr[i], i ]); } // Sort the vector in ascending order. v = v.sort(); // Stores the total cost var ans = 0; // Stores the index of last element visited var last = 0; // Traverse the vector v for (var i = 0; i < N; i++) { // Increment ans ans += Math.abs(v[i][1] - last); // Assign last = v[i][1]; } // Return ans return ans;}// Driver Codevar arr = [ 4, 3, 2, 5, 1 ];var N = arr.length;document.write(calculateDistance(arr, N));// This code is contributed by Shubhamsingh10</script> |
Output:
11
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
