Author: Rishav Pati
Tester: Rajat De
Editorialist: Sidhant Bansal
Difficulty : Cakewalk - Easy
Expected Complexity: O(A_MAX * N * N)
The array should be an arithmetic progression with common difference 1, ie. more formally A[i] - A[i - 1] = 1, for all i from 2 to N
As N <= 50 and A[i] <= 50 we can do a naive brute force.
We can assume the first element to be from the values 0 to S where S is the sum of all the elements of array A.
- For each starting element we build the entire AP of the array in O(N), let this array be B and check weather the sum of all these elements is equal to S.
- If Yes, then we can calculate the minm no. of steps to do this by maintaining a variable RESULT, initialize RESULT to 0.
- Wherever we find that B[i] > A[i], add (B[i] - A[i]) to RESULT.
ANSWER = INT_MAX FOR i = 0 to S (where S is the sum of array A) B[ 1 ] = i SUM = B [ 1 ] FOR j = 2 to N B[j] = B[j - 1] + 1 SUM = SUM + B[j] IF SUM = S RESULT = 0 FOR j = 1 to N IF B[j] > A[j] RESULT = RESULT + (B[j] - A[j]) ANSWER = MIN(ANSWER, RESULT) IF ANSWER = INT_MAX PRINT -1 ELSE PRINT ANSWER
Complexity analysis - O(A_MAX * N * N), as S = A_MAX * N in the worst case and the checking of array B is O(N).