Split a number into K unique parts such that their GCD is maximum

We are given a number N and we need to split it into K numbers (let's say A1, A2. ..., Ak) such that (Ai == Aj only when i==j) and sum of them equals N. We need to find these numbers such that GCD of the the numbers is maximum.

Mathematically:

• Split N into k numbers A1, A2, ..., Ak such that:
  • A1 + A2 + ... + Ak = N
  • GCD(A1, A2, ..., Ak) is maximum

Approach

First we will find about how will we get maximum GCD.

By definition of GCD a number a is GCD of (A1,A2,..Ak) is that a is factor of all of these numbers.

Hence a number Ai can be written as Ai = a * Bi.....(1).
now since A1 + A2 + ....+ Ak = N.....(2).
Now we use (1) in (2) to get:

a * (B1 + B2 + .... + Bk) = N

for a to be maximum we need to minimize sum of values of Bi.

Since, every number is unique hence every Bi is unique as well.

so, we can easily assume that B1 + B2 + ... + Bk >= 1 + 2 + 3... + k.

B1 + B2 + ... + Bk >= 1 + 2 + 3... + k

since every value is unique so we assigned least permissible value to everyone.
hence, min(B1 + B2 + ... +Bk) = (k(k + 1)) / 2 = minimum_number.
so maximum value of a can be N/(minimum_number).

min(B1 + B2 + ... +Bk) = (k(k + 1)) / 2 = M

a = N/M

but a also has to be an integer, so we can iteratively find the maximum
GCD by finding the least number greater than minimum_number which also divides N.

Implementation

Following is the C++ implementation of our approach:

// Part of OpenGenus IQ
#include <iostream>
using namespace std;

// function to find maximum GCD
int findMaxGCD(int n, int k) {
    int minimum_number = (k * (k + 1) ) / 2;
    
    // returning -1 if n can't be split into k unique numbers
    if(n < minimum_number) {
        return -1;
    }
    // the first number that will divide n will give our greatest GCD
    for(int i = minimum_number, i <= n; i++) {
        if(n % i == 0) {
            return n / i;
        }
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << findMaxGCD(n, k) << "\n;
}

Time Complexity - O(N) where N is the number

Note that i ran loop till i equals n so that i get 1 as maximum when nothing else is there( you can take n=6,k=3 for the case)

we can move forward to getting the number's split. now that we found greatest GCD we can surely find the sum of Bi's.

let it be b.
so, b = n / a
since, B1 + B2 + B3 + ... + Bk = b.

One trivial solution to this is to assign B1 =1, B2 =2, till Bk-1 =k-1,
and Bk = b - (k(k - 1))/2 or Bk= remaining number from sum after assigning others in the given way, this way we maintained uniqueness as well as sum property at same time.

Now you can use (1) to easily find the sequence A1, A2, .., Ak.

Note

we can easily optimize this algorithm to O(sqrt(n)) by using complementary property of two numbers.

If x * y = N then x = N / y and one of x or y will be less than or equal to sqrt(n) and other will be greater or equal to sqrt(n).

Optimized Implementation

// Part of OpenGenus IQ
// optimized algorithm 

#include <iostream>
using namespace std;

// function to find maximum GCD
int findMaxGCD(int n, int k) {
    int minimum_number = (k * (k + 1) ) / 2;
    
    if(n < minimum_number) {
        return -1;
    }
    
    int result=0;
    
    // using complementary number's property
    int i = sqrt(n);
    while(i >= 1) {
        if(n % i == 0) {
            if(i >= minimum_number) {
                res = max(result, n / i);
            }
            if(n / i >= minimum_number) {
                result = max(result, i);
            }
        }
    }
    return result;
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << findMaxGCD(n, k) << "\n";
}

Time Complexity - O(sqrt(n)) - since i is going from sqrt(n) to 1 in the iteration, which optimizes it to great extent.

So, that's it!, hope you found it useful! Happy Coding :)

Learn more:

• List of Greedy algorithms at OpenGenus
• List of Mathematical algorithms at OpenGenus