while reading the question i didn’t see the constraint on the value of “a” so i ended up trying to generate a solution for a general value of a
here is the code
i wanted to know if the code could be optimized further cause the code i wrote looks terrible also please let me know if my logic in the code is correct or not because the test cases are probably not that diverse so i could be missing something…
(for a general “a” we also need to minimize the number of elements which we have to add to make it nice)
My logic : a nice array is an array in which all elements are in an AP with the first element as the common diff of the AP
(but then I ran into the input 2 6 so instead of first term being common diff i made it min(min_ele , common diff)
The code couldn’t be optimised from O(Max(A[i])) I think . The reason being just consider the Input array : 1,2,4,8,16… , For this array you need every number till Max(A[i])
i meant optimizing in the sense that in my code i am finding GCD of 4 numbers n(n+1)/2 times as finding GCD is already a heavy operation for big numbers is there any way around that…
and my code have a complexity of O(n^2) do you have way to do it in O(max a[i]) ??