PROBLEM LINK:
Author: Puneet Gupta
Editorialist: Puneet Gupta
DIFFICULTY:
EASY
PREREQUISITES:
GREEDY, IMPLEMENTATION, SORTING
PROBLEM:
Given a sequence of integers A1, A2, ..., AN, count the minimum number of moves needed to build a permutation, provided in one move, you are allowed to decrease or increase any number by one
EXPLANATION:
The solution of the problem is rather simple. Sort all integers a and then make integer 1 from a[1], integer 2 from a[2] and so on.
So, integer a[i] adds to the answer the value |a[i] - i|. The answer should be count in 64-bit type. You can simply guess why such solution is correct.
AUTHOR’S SOLUTION:
Author’s solution can be found here.