Given n numbers, what's the maximum GCD of the array that can we get after using at most k operations?
The only operation we can do at most k times, is to choose a number from the array and increment it by 1.
1 <= n <= 10^5
1 <= a_i <= 10^5
1 <= k <= 10^18
my approach was trying every number x smaller than the largest number in the array and count minimum operations to make each number divisible by x and if it possible then update my answer. now if the answer larger than or equal the largest then all numbers of the array must be equal, and the answer will be (k-sum)/n
this is my code
i could solve this problem with these constraints but what if the numbers in the array were up to 10^9 or even 10^18, can anyone help me with the new constraints?
.
if mid take x operation, this does not mean mid+1 must take larger number of operations
But how do you iterate $$$x$$$ for this inputs:
Shouldn't it take quadratic time?
No, it is Harmonic series, i just iterate over the multiples of x, between every Mutiple i*x and (i-1) *x.
i calculate the numbers of integers in the array in this range and let's call it A and their sum and
call it B then these numbers need i*x*A — B.
i do this until i reach to a multiple larger than the Max number in the array. this takes n*log(n)
Multiples of what? How it aligns with original post where you explicitly stated that "trying every number x smaller than the largest"?
For input like a=[6,13], k=2 answer is not multiple of anything from input.
Forall x, iterate the multiple of x. The time conplexity is approx. $$$O(A\log A)$$$, where $$$A=\max{a}$$$.
But why would you do that? And counting number of operations to get gcd x is $$$O(n)$$$, so total complexity is $$$O(n^2log n)$$$
If k >= number of operations to get $$$max(a)$$$ then you can get answer in $$$O(1)$$$ using formula from original post $$$(k-sum)/n$$$. But if it's less there is no point iterating multiples of every value from 1..max(a), iterate it just once, but it's = $$$O(max(a)n)$$$
the answer may be less than max(a) so i iterate multiple of every value. counting number of operations to get GCD x takes max(a)/x so iterating over all multiple of every number will be O(max(a)*log(max(a))) think about it as sieve of Eratosthenes. I added the source code if you would like to read it
Nice way to use prefix sum, now I got your idea.
Auto comment: topic has been updated by Khalell (previous revision, new revision, compare).