Concepts Used

Sorting

Difficulty Level

Medium

Problem Statement (Simplified):

We need to find the total number of steps need to make the current array of size N same as an array containing 1 to N numbers as elements. Each decrement or increment is counted as a step.

See original problem statement here

Test Case:

Input:
1
5
8 4 2 1 9

Output:
9

Explanation:
As our target array is [1,2,3,4,5], we already have 1, 2, and 4 in our array. We have 8 and 9 in place of 3 and 5, so if convert 8 to 3, and 9 to 5, we can achieve target array. Hence minimum increments/decrements required will be (8-3)+(9-5) ways i.e. 9 ways.

Solving Approach :

  • Observation: We can see that size of array goes from 1 to 10^6, in worse conditions let the size of the array be 10^6 if we sort this array using any of sorting techniques i.e. Bubble Sort, Insertion Sort, Selection sort. They all take O(N^2) in the worst cases, which results in 10^12 iterations when the size of the array is 10^6. So we, can't choose the above three sorting algorithms. We use Merge Sort to sort array as it sorts array in linearithmic time complexity (nlog(n)).
  • By sorting the given array in non-decreasing order, it will make sure that the difference between element at current index and Hero array's (Target array) element is minimum.
  • Thus we can take the absolute difference between both elements, an increment or decrement, both will be taken as a step.
  • Sum of all absolute differences is our final answer.

Example

Let the arrays be,

Sorting array A as absolute difference will be even and minimized,

On,sorting A, A becomes,

Now, both arrays according to data structures and algorithms tutorials, and save absolute difference ob elements at same indexes in a variable sum initially set to 0.

For index i, i=0

A[i] = 1, heroArray[i] = 1

sum = sum + | A[i] - heroArray[i] |

sum = 0 + | 1 - 1 |

sum = 0 + 0

sum = 0

For index i, i=1

A[i] = 2, heroArray[i] = 2

sum = sum + | A[i] - heroArray[i] |

sum = 0 + | 2 - 2 |

sum = 0 + 0

sum = 0

For index i, i=2

A[i] = 4, heroArray[i] = 3

sum = sum + | A[i] - heroArray[i] |

sum = 0 + | 4 - 3 |

sum = 0 + 1

sum = 1

For index i, i=3

A[i] = 8, heroArray[i] = 4

sum = sum + | A[i] - heroArray[i] |

sum = 1 + | 8 - 4 |

sum = 1 + 4

sum = 5

For index i, i=4

A[i] = 9, heroArray[i] = 5

sum = sum + | A[i] - heroArray[i] |

sum = 5 + | 9 - 5 |

sum = 5 + 4

sum = 9

Hence sum is our final answer.

Solutions


#include <stdio.h>
#include<stdlib.h>

void merge(int arr[], int start, int mid, int end){
    int left[mid-start+1];
    int right[end-mid];
    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

}

void mergeSort(int arr[], int start, int end){
    if(end==start)
        return;
    mergeSort(arr,start,(start+end)/2);
    mergeSort(arr,((start+end)/2)+1,end);
    merge(arr,start,(start+end)/2,end);
}

int main()
{

  int test;
  scanf("%d",&test);

  while(test--){

      int n;
    scanf("%d",&n);

    int a[n];

    for(int i=0;i<n;i++)
      scanf("%d",&a[i]);

    mergeSort(a,0,n-1);

    long long int cost=0;

    for(int i=0;i<n;i++)
      cost+= abs(a[i]-(i+1));

    printf("%lld\n", cost);
  }
}

#include <bits/stdc++.h>
using namespace std;

void merge(int arr[], int start, int mid, int end){
    int left[mid-start+1];
    int right[end-mid];
    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

}

void mergeSort(int arr[], int start, int end){
    if(end==start)
        return;
    mergeSort(arr,start,(start+end)/2);
    mergeSort(arr,((start+end)/2)+1,end);
    merge(arr,start,(start+end)/2,end);
}

int main()
{  

  int test;
  cin>>test;
  while(test--){

      int n;
      cin>>n;

    int a[n];
    for(int i=0;i<n;i++)
      cin>>a[i];
    mergeSort(a,0,n-1);

    long long int cost=0;
    for(int i=0;i<n;i++)
      cost+=abs(a[i]-(i+1));

    cout<<cost<<endl;
  }
}

import java.util.*;
import java.io.*;

public class Main {
  static void merge(int arr[], int start, int mid, int end){
    int left[] = new int[mid-start+1];
    int right[] = new int[end-mid];
    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

}

  static void mergeSort(int arr[], int start, int end){
      if(end==start)
          return;
      mergeSort(arr,start,(start+end)/2);
      mergeSort(arr,((start+end)/2)+1,end);
      merge(arr,start,(start+end)/2,end);
  }

  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int test = sc.nextInt();

    while(test--!=0){

        int n = sc.nextInt();

      int a[] = new int[n];

      for(int i=0;i<n;i++)
        a[i] = sc.nextInt();

      mergeSort(a,0,n-1);

      long cost=0;

      for(int i=0;i<n;i++)
        cost+= Math.abs(a[i]-(i+1));

      System.out.println(cost);
    }

  }
}

where N is length of array

Space Complexity : O(1)

Previous post Plagiarism Test
Next post Aman Arithmetic progression

Leave a Reply

Your email address will not be published. Required fields are marked *