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 106, in worse conditions let the size of the array be 106 if we sort this array using any of sorting techniques i.e. Bubble Sort, Insertion Sort, Selection sort. They all take O(n2) in the worst cases, which results in 1012 iterations when the size of the array is 106. 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,

Now, we iterate on both arrays, and save absolute difference ob elements at same indexes in a variable sum initially set to 0.

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);
    }

  }
}
def merge(arr, start, mid, end):
	left = [0 for i in range(mid - start + 1)]
	right = [0 for i in range(end - mid)]
	
	for i in range(start, mid + 1):
		left[i - start] =  arr[i]
	
	for i in range(mid + 1, end + 1):
		right[i - (mid + 1)] = arr[i]
	
	leftIndex = 0
	rightIndex = 0
	arrIndex = start
	
	while leftIndex <= mid - start and rightIndex < end - mid:
	
		if(left[leftIndex] < right[rightIndex]):
			arr[arrIndex] = left[leftIndex]
			leftIndex += 1
		
		else:
			arr[arrIndex] = right[rightIndex]
			rightIndex += 1
		
		arrIndex += 1
	
	while(leftIndex <= mid - start):
		arr[arrIndex] = left[leftIndex]
		leftIndex += 1
		arrIndex += 1
	
	while(rightIndex < end - mid):
		arr[arrIndex] = right[rightIndex]
		rightIndex += 1
		arrIndex += 1
	
def mergeSort(arr, start, 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)


for _ in range(int(input())):

	n = int(input())
	a = list(map(int, input().split()))
	mergeSort(a, 0, n - 1)

	cost = 0
	for i in range(n):
		cost += abs(a[i] - (i + 1))

	print(cost)


Space Complexity : O(1)

where N is length of array

[forminator_quiz id="1342"]

So, in this blog, we have tried to explain sorting in the most optimal way. If you want to solve more questions on sorting, which are curated by our expert mentors at PrepBytes, you can follow this sorting.

Leave a Reply

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