I got this question for company coding test and couldn't solve it

Question :

An array A of size N is given.

In one operation, you can take any non-empty subarray and increment all numbers in that subarray by 1.

You can perform the increment operation on the subarray as many times as needed.

Find the minimum operations to increment and make all numbers in the array to the nearest perfect square.

I am unable to think of a way to approach the problem. Please help.

You can generate another array B of size N, such that for each index i between 1 and N inclusive, B[i] = minimum non-negative increment such that A[i]+B[i] is a prefect square.

The problem is then reduced to finding the minimum number of operations required to make all items in the array B equal to zero, where each operation takes any non-empty subarray in B with non-zero elements, and decrement all items in that subarray by 1.

A greedy approach for solving the reduced problem is to recursively find maximum length subarrays in B with positive values, and to find the minimum value in each subarray. Subtracting the minimum value of the maximum length subarray from each item in it generates at least one new zero in B, and generates new maximum length subarray(s) until all items become zero.

1 Like