Company: Myntra
Difficulty: medium
Again Optimize You are given an array(1-based indexing) of positive integers of length N. You need to find a value X such that sum of |A[i]-X-i| over all 0 ≤ i Input Format The first line of input contains a single integer N representing the size of array. The second line contains N integers representing elements of the array. Output Format Print a single integer representing the minimum summation. Constraints 1 ≤ N ≤ 10 8 0 ≤ A[i] ≤ 10 8 Sample Test Cases Sample Testcase 1 Input: 5 2 4 1 5 3 Output: 7 Explanation: Given input: Array size: 5 Array elements: 2, 4, 1, 5, 3 We need to find a value X that minimizes the sum of |A[i] - X - i| for all i in the array. Calculating the individual terms for each index: For i = 0: (|2 - X - 0| = |2 - X|) For i = 1: (|4 - X - 1| = |3 - X|) For i = 2: (|1 - X - 2| = |-1 - X| = |X + 1|) For i = 3: (|5 - X - 3| = |2 - X|) For i = 4: (|3 - X - 4| = |-1 - X| = |X + 1|) Now, the total sum can be expressed as: S(X) = |2 - X| + |3 - X| + |X + 1| + |2 - X|