Help needed in a codeforces question

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)

You can look at my code having O(Max(N,Max(A[i])) Time complexity Code

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]) ??

1 Like

See the comment I deleted once :sweat_smile:

we need to minimize the num of element we add as well
example input : 4 12

your code will give
1 2 3 4 … 12
my code will give
4 8 12

in your code if max a[i] id greater than 300 its alwyas impossible as the max elements we can have in the arr 300

Ohh okay I didn’t read that part of your statement :sweat_smile:

i had a hunch seeing the code in the deleted comment that you did so i had edited my post to include that info…
:sweat_smile:

An O(Max(Nlog(Max(A[i])),Max(a[i]))) code . The main idea is GCD(a,b)=GCD(a,a-b);

really sorry for the very late reply…
but i get what you mean instead of running the gcd function n^2 times runnning it n time is sufficient …

thanks a lot

1 Like