Series with largest GCD and sum equals to n
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)
Contact Us