Khalell's blog

Maximum GCD after at most k operation
By Khalell, history, 6 months ago, In English

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?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
6 months ago, # |
← Rev. 2   Vote: I like it -36 Vote: I do not like it

.

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    if mid take x operation, this does not mean mid+1 must take larger number of operations

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

But how do you iterate $$$x$$$ for this inputs:

  1. n=1e5, a=[1, 1, …, 1, 100000], k=1e5
  2. n=1e5, a=[1, 2, …, 99999, 100000], k=50000

Shouldn't it take quadratic time?

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 months ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        Forall x, iterate the multiple of x. The time conplexity is approx. $$$O(A\log A)$$$, where $$$A=\max{a}$$$.

        → Reply
        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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)$$$

          → Reply
          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              Nice way to use prefix sum, now I got your idea.

              → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Khalell (previous revision, new revision, compare).

→ Reply