Approach
Let 'A' be the target array that contains all the elements from 1 to N in the sorted order and 'B' be the given array.
Observation 1: If you sort the given array, you can ensure that the difference of B[i] and A[i] for every i from 1 to N is minimum.
Observation 2: If we take the absolute value of differences, both increment and decrement operations are the same.
Observation 3: The final answer is the sum of the absolute value of differences.
Observation 4: The range of N is 0 to 10^5. So we can't use bubble sort, insertion sort, and selection sort to sort the given array because they work in O(N^2) time complexity, so in the worst case, the total number of operations goes up to 10^10, which is inefficient.
Observation 5: We can use merge sort or quicksort as it works in O(NlogN) time complexity. We can also use the inbuilt sorting functions.
Example
Code
//merge sort
void merge(int B[], int start, int mid, int end){
int lft[mid - start + 1];
int rgt[end - mid];
for(int i = start; i < mid + 1; i++){
lft[i - start] = B[i];
}
for(int i = mid + 1; i <= end; i++){
rgt[i - (mid + 1)] = B[i];
}
int lftIndex = 0, rgtIndex = 0, ind = start;
for( ; lftIndex <= mid - start && rgtIndex < end - mid; ind++){
if(lft[lftIndex] < rgt[rgtIndex]){
B[ind] = lft[lftIndex++];
}
else{
B[ind] = rgt[rgtIndex++];
}
}
while(lftIndex <= mid - start){
B[ind++] = lft[lftIndex++];
}
while(rgtIndex < end - mid){
B[ind++] = rgt[rgtIndex++];
}
}
void mergeSort(int B[], int start, int end){
if(end <= start)
return;
mergeSort(B, start, (start + end)/2);
mergeSort(B, ((start + end)/2) + 1, end);
merge(B, start, (start + end)/2, end);
}
signed main(){
int N;
cin >> N;
int B[N + 3] = {}; //input array
for(int i = 1; i <= N; ++i){
cin >> B[i];
}
mergeSort(B, 1, N); //sorting using merge sort
int ans = 0;
for(int i = 1; i <= N; i++){
ans += abs(i - B[i]);
}
cout << ans << "\n";
}
Also Read - Selection Sort in C
Dry Run
Input : N = 6
B = 1 5 2 8 3 10 //0 based indexing
Apply merge sort on B
B = 1 2 3 5 8 10
ans = 0
For ( i = 1 to i = N)
i = 0, ans = ans + |1 - 1| = 0 + 0 = 0
i = 1, ans = ans + |2 - 2| = 0 + 0 = 0
i = 3, ans = ans + |3 - 3| = 0 + 0 = 0
i = 4, ans = ans + |4 - 5| = 0 + 1 = 1
i = 5, ans = ans + |5 - 8| = 1 + 3 = 4
i = 6, ans = ans + |6 - 10| = 4 + 4 = 8
Hence, the final answer is 8
Time Complexity
Merge sort takes O(N log N) time, and extra O(N) time is needed to find the sum of differences. So the overall time complexity is O(N log N + N).
Read More - Time Complexity of Sorting Algorithms
Space Complexity
If we use merge sort, we need an extra array of size N. So, in that case, the space complexity is O(N). But, if we use quicksort with appropriate pivot, the space complexity can be reduced to O(logN).
FAQs
Q1. What is merge sort?
Merge sort is one of the most efficient sorting techniques. It follows divide and conquer strategy. It first divides the original array into N subarrays of size one each and then repeatedly merges two in sorted order.
Q2. What is the time complexity of merge sort?
The time complexity of merge sort is O(N logN).
Q3. What is quicksort?
Merge sort is one of the most efficient sorting techniques. It follows divide and conquer strategy. It first divides the original array into N subarrays of size one each and then repeatedly merges two in sorted order. The time complexity of quicksort is also O(N logN).
Key Takeaways
In this article, we solved a problem by using the sorting algorithms. Having a good grasp of sorting algorithms is very important to crack the coding interviews. Check out this coding ninjas blog on sorting algorithms for getting a better hold on it.
Recommended Problems -
Also check out - Inorder Predecessor
To learn more about such data structures and algorithms, Coding Ninjas Studio is a one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies by providing Online Mock Test Series and many more benefits.
Happy learning!
By Abhishek Ranjan
12+ registered 
