Last Updated on June 17, 2022 by Ria Pathak
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
Nsame as an array containing 1 toNnumbers 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
suminitially set to0.
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
Nis 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.