Series with largest GCD and sum equals to n

Last Updated : 18 Sep, 2023

Given an integer n, print m increasing numbers such that the sum of m numbers is equal to n and the GCD of m numbers is maximum among all series possible. If no series is possible then print “-1”.
Examples :

Input  : n = 24,
         m = 3  
Output : 4 8 12  
Explanation : (3, 6, 15) is also a series 
of m numbers which sums to N, but gcd = 3
(4, 8, 12) has gcd = 4 which is the maximum
possible.
              
Input  : n = 6 
         m = 4 
Output : -1 
Explanation: It is not possible as the 
least GCD sequence will be 1+2+3+4 which
is greater than n, hence print -1.

Approach:
The most common observation is that the gcd of the series will always be a divisor of n. The maximum gcd possible (say b) will be n/sum, where sum is the sum of 1+2+..m.
If b turns out to be 0, then the sum of 1+2+3..+k exceeds n which is invalid, hence output “-1”.
Traverse to find out all the divisors possible, a loop till sqrt(n). If the current divisor is i, the best possible way to take the series will be to consider i, 2*i, 3*i, …(m-1)*i, and their sum is s which is equal to i * (m*(m-1))/2 . The last number will be n-s.
Along with i being the divisor, n/i will be the other divisor so check for that also.
Take maximum of possible divisor possible (say r) which should be less than or equals to b and print the sequence as r, 2*r, … (m-1)*r, n—s.
If no such divisors are found simply output “-1”.

C++

// CPP program to find the series with largest 
// GCD and sum equals to n 
#include <bits/stdc++.h> 
using namespace std; 
  
// function to generate and print the sequence 
void print_sequence(int n, int k) 
{ 
    // stores the maximum gcd that can be 
    // possible of sequence. 
    int b = n / (k * (k + 1) / 2); 
  
    // if maximum gcd comes out to be 
    // zero then not possible 
    if (b == 0) { 
        cout << -1 << endl; 
  
    } else { 
  
        // the smallest gcd possible is 1 
        int r = 1; 
  
        // traverse the array to find out  
        // the max gcd possible 
        for (int x = 1; x * x <= n; x++) { 
  
            // checks if the number is  
            // divisible or not 
            if (n % x != 0) 
                continue; 
  
            // checks if x is smaller than  
            // the max gcd possible and x  
            // is greater than the resultant  
            // gcd till now, then r=x 
            if (x <= b && x > r) 
                r = x; 
  
            // checks if n/x is smaller than  
            // the max gcd possible and n/x  
            // is greater than the resultant  
            // gcd till now, then r=x 
            if (n / x <= b && n / x > r) 
                r = n / x; 
        } 
  
        // traverses and prints d, 2d, 3d, 
        // ..., (k-1)·d, 
        for (int i = 1; i < k; i++) 
            cout << r * i << " "; 
  
        // computes the last element of 
        // the sequence n-s. 
        int res = n - (r * (k * (k - 1) / 2)); 
  
        // prints the last element 
        cout << res << endl; 
    } 
} 
  
// driver program to test the above function 
int main() 
{ 
    int n = 24; 
    int k = 4; 
    print_sequence(n, k); 
  
    n = 24, k = 5; 
    print_sequence(n, k); 
  
    n = 6, k = 4; 
    print_sequence(n, k); 
} 

Java

// Java program to find the series with  
// largest GCD and sum equals to n 
import java.io.*; 
  
class GFG { 
  
// function to generate and print the sequence 
static void print_sequence(int n, int k) 
{ 
    // stores the maximum gcd that can be 
    // possible of sequence. 
    int b = n / (k * (k + 1) / 2); 
  
    // if maximum gcd comes out to be 
    // zero then not possible 
    if (b == 0) { 
        System.out.println("-1"); 
  
    } else { 
  
        // the smallest gcd possible is 1 
        int r = 1; 
  
        // traverse the array to find out  
        // the max gcd possible 
        for (int x = 1; x * x <= n; x++) { 
  
            // checks if the number is  
            // divisible or not 
            if (n % x != 0) 
                continue; 
  
            // checks if x is smaller than  
            // the max gcd possible and x  
            // is greater than the resultant  
            // gcd till now, then r=x 
            if (x <= b && x > r) 
                r = x; 
  
            // checks if n/x is smaller than  
            // the max gcd possible and n/x  
            // is greater than the resultant  
            // gcd till now, then r=x 
            if (n / x <= b && n / x > r) 
                r = n / x; 
        } 
  
        // traverses and prints d, 2d, 3d,..., (k-1) 
        for (int i = 1; i < k; i++) 
            System.out.print(r * i + " "); 
  
        // computes the last element of 
        // the sequence n-s. 
        int res = n - (r * (k * (k - 1) / 2)); 
  
        // prints the last element 
        System.out.println(res); 
    } 
} 
  
// driver program to test the above function 
public static void main(String[] args) 
{ 
    int n = 24; 
    int k = 4; 
    print_sequence(n, k); 
  
    n = 24; k = 5; 
    print_sequence(n, k); 
  
    n = 6; k = 4; 
    print_sequence(n, k); 
} 
} 
  
// This code is contributed by Prerna Saini 

Python3

# Python3 code to find the series  
# with largest GCD and sum equals to n 
  
def print_sequence(n, k): 
      
    # stores the maximum gcd that 
    # can be possible of sequence. 
      
    b = int(n / (k * (k + 1) / 2)); 
      
  
    # if maximum gcd comes out to be 
    # zero then not possible 
      
    if b == 0: 
        print ("-1") 
  
    else: 
        # the smallest gcd possible is 1 
        r = 1; 
  
        # traverse the array to find out  
        # the max gcd possible 
        x = 1
          
        while x ** 2 <= n: 
              
            # checks if the number is  
            # divisible or not 
            if n % x != 0: 
              
                # x = x + 1 
                continue; 
                  
              
            # checks if x is smaller than  
            # the max gcd possible and x  
            # is greater than the resultant  
            # gcd till now, then r=x 
            elif x <= b and x > r: 
                r = x 
                # x = x + 1 
  
            # checks if n/x is smaller than  
            # the max gcd possible and n/x  
            # is greater than the resultant  
            # gcd till now, then r=x 
            elif n / x <= b and n / x > r : 
                r = n / x 
                # x = x + 1 
                  
            x = x + 1
          
  
    # traverses and prints d, 2d, 3d, 
    # ..., (k-1)·d, 
        i = 1
        while i < k : 
            print (r * i, end = " ") 
            i = i + 1
              
        last_term = n - (r * (k * (k - 1) / 2)) 
        print (last_term) 
          
          
              
          
# main driver 
print_sequence(24,4)  
print_sequence(24,5) 
print_sequence(6,4) 
  
# This code is contributed by Saloni Gupta 

C#

// C# program to find the series with  
// largest GCD and sum equals to n 
using System; 
  
class GFG { 
  
// function to generate and 
// print the sequence 
static void print_sequence(int n, int k) 
{ 
      
    // stores the maximum gcd that can be 
    // possible of sequence. 
    int b = n / (k * (k + 1) / 2); 
  
    // if maximum gcd comes out to be 
    // zero then not possible 
    if (b == 0) 
    { 
        Console.Write("-1"); 
  
    } 
    else 
    { 
  
        // the smallest gcd possible is 1 
        int r = 1; 
  
        // traverse the array to find out  
        // the max gcd possible 
        for (int x = 1; x * x <= n; x++) 
        { 
  
            // checks if the number is  
            // divisible or not 
            if (n % x != 0) 
                continue; 
  
            // checks if x is smaller than  
            // the max gcd possible and x  
            // is greater than the resultant  
            // gcd till now, then r=x 
            if (x <= b && x > r) 
                r = x; 
  
            // checks if n/x is smaller than  
            // the max gcd possible and n/x  
            // is greater than the resultant  
            // gcd till now, then r=x 
            if (n / x <= b && n / x > r) 
                r = n / x; 
        } 
  
        // traverses and prints d, 2d, 
        // 3d,..., (k-1) 
        for (int i = 1; i < k; i++) 
        Console.Write(r * i + " "); 
  
        // computes the last element of 
        // the sequence n-s. 
        int res = n - (r * (k *  
                  (k - 1) / 2)); 
  
        // prints the last element 
        Console.WriteLine(res); 
    } 
} 
  
// Driver Code 
public static void Main() 
{ 
    int n = 24; 
    int k = 4; 
    print_sequence(n, k); 
  
    n = 24; k = 5; 
    print_sequence(n, k); 
  
    n = 6; k = 4; 
    print_sequence(n, k); 
} 
} 
  
// This code is contributed by Nitin Mittal. 

PHP

<?php 
// PHP program to find the  
// series with largest GCD  
// and sum equals to n 
  
// function to generate and 
// print the sequence 
function print_sequence($n, $k) 
{ 
    // stores the maximum gcd that  
    // can be possible of sequence. 
    $b = (int)($n / ($k * ($k + 1) / 2)); 
  
    // if maximum gcd comes out to be 
    // zero then not possible 
    if ($b == 0)  
    { 
        echo(-1); 
    }  
    else 
    { 
  
        // the smallest gcd possible is 1 
        $r = 1; 
  
        // traverse the array to find out  
        // the max gcd possible 
        for ($x = 1; $x * $x <= $n; $x++)  
        { 
  
            // checks if the number is  
            // divisible or not 
            if ($n % $x != 0) 
                continue; 
  
            // checks if x is smaller than  
            // the max gcd possible and x  
            // is greater than the resultant  
            // gcd till now, then r=x 
            if ($x <= $b && $x > $r) 
                $r = $x; 
  
            // checks if n/x is smaller than  
            // the max gcd possible and n/x  
            // is greater than the resultant  
            // gcd till now, then r=x 
            if ($n / $x <= $b && $n / $x > $r) 
                $r = $n / $x; 
        } 
  
        // traverses and prints d, 2d, 3d, 
        // ..., (k-1)·d, 
        for ($i = 1; $i < $k; $i++) 
            echo($r * $i . " "); 
  
        // computes the last element of 
        // the sequence n-s. 
        $res = $n - ($r * ($k * ($k - 1) / 2)); 
  
        // prints the last element 
        echo($res . "\n"); 
    } 
} 
  
// Driver Code 
$n = 24; 
$k = 4; 
print_sequence($n, $k); 
  
$n = 24; $k = 5; 
print_sequence($n, $k); 
  
$n = 6; $k = 4; 
print_sequence($n, $k); 
  
// This code is contributed by Ajit. 
?> 

Javascript

<script> 
  
// Javascript program to find the  
// series with largest GCD  
// and sum equals to n 
  
// function to generate and 
// print the sequence 
function print_sequence(n, k) 
{ 
    // stores the maximum gcd that  
    // can be possible of sequence. 
    let b = parseInt(n / (k * (k + 1) / 2)); 
  
    // if maximum gcd comes out to be 
    // zero then not possible 
    if (b == 0)  
    { 
        document.write(-1); 
    }  
    else 
    { 
  
        // the smallest gcd possible is 1 
        let r = 1; 
  
        // traverse the array to find out  
        // the max gcd possible 
        for (let x = 1; x * x <= n; x++)  
        { 
  
            // checks if the number is  
            // divisible or not 
            if (n % x != 0) 
                continue; 
  
            // checks if x is smaller than  
            // the max gcd possible and x  
            // is greater than the resultant  
            // gcd till now, then r=x 
            if (x <= b && x > r) 
                r = x; 
  
            // checks if n/x is smaller than  
            // the max gcd possible and n/x  
            // is greater than the resultant  
            // gcd till now, then r=x 
            if (n / x <= b && n / x > r) 
                r = n / x; 
        } 
  
        // traverses and prints d, 2d, 3d, 
        // ..., (k-1)·d, 
        for (let i = 1; i < k; i++) 
            document.write(r * i + " "); 
  
        // computes the last element of 
        // the sequence n-s. 
        let res = n - (r * (k * (k - 1) / 2)); 
  
        // prints the last element 
        document.write(res + "<br>"); 
    } 
} 
  
// Driver Code 
let n = 24; 
let k = 4; 
print_sequence(n, k); 
  
n = 24;  
k = 5; 
print_sequence(n, k); 
  
n = 6;  
k = 4; 
print_sequence(n, k); 
  
// This code is contributed by _saurabh_jaiswal. 
  
</script>

Output :

2 4 6 12
1 2 3 4 14
-1

Time complexity: O( sqrt (n) )
Auxiliary Space: O(1)

Program to find GCD of floating point numbers

GeeksforGeeks

Improve

Series with largest GCD and sum equals to n

C++

Java

Python3

C#

PHP

Javascript

Similar Reads

Problems on GCD

Problems on LCM

Problems on Euler Totient

What kind of Experience do you want to share?