Given a positive integer N, the task is to divide it into K unique parts such that the sum of these parts is equal to the original number and the gcd of all the parts is maximum. Print the maximum gcd if such a division exists else print -1.
Examples:
Input: N = 6, K = 3
Output: 1
Only possible division with unique
elements are (1, 2, 3) and gcd(1, 2, 3) = 1.
Input: N = 18, K = 3
Output: 3
Naive approach: Find all the possible divisions of N and compute the maximum gcd of them. But this approach will take exponential time and space.
Efficient approach: Let the divisions of N be A1, A2……..AK
Now, it is known that gcd(a, b) = gcd(a, b, a + b) and hence, gcd(A1, A2….AK) = gcd(A1, A2….AK, A1 + A2…. + AK)
But A1 + A2…. + AK = N and hence, the gcd of the divisions will be one of the factors of N.
Let a be the factor of N which can be the possible answer:
Since a is the gcd, all the division will be the multiples of a and hence, for K unique Bi,
a * B1 + a * B2……. + a * BK = N
a * (B1 + B2…….+ BK) = N
Since all the Bi are unique,
B1 + B2…….+ BK ? 1 + 2 + 3 ….. + K
B1 + B2…….+ BK ? K * (K + 1) / 2
Hence, all the factors of N whose complementary factor is greater than or equal to K * (K + 1) / 2 can be one of the possible answers, and we have taken to the maximum of all the possible answers.
Below is the implementation of the above approach:
CPP
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to calculate maximum GCDint maxGCD(int N, int K){ // Minimum possible sum for // K unique positive integers int minSum = (K * (K + 1)) / 2; // It is not possible to divide // N into K unique parts if (N < minSum) return -1; // All the factors greater than sqrt(N) // are complementary of the factors less // than sqrt(N) int i = sqrt(N); int res = 1; while (i >= 1) { // If i is a factor of N if (N % i == 0) { if (i >= minSum) res = max(res, N / i); if (N / i >= minSum) res = max(res, i); } i--; } return res;}// Driver codeint main(){ int N = 18, K = 3; cout << maxGCD(N, K); return 0;} |
Java
// Java implementation of the approachimport java.io.*;import java.lang.Math; class GFG{ // Function to calculate maximum GCD static int maxGCD(int N, int K) { // Minimum possible sum for // K unique positive integers int minSum = (K * (K + 1)) / 2; // It is not possible to divide // N into K unique parts if (N < minSum) return -1; // All the factors greater than sqrt(N) // are complementary of the factors less // than sqrt(N) int i = (int) Math.sqrt(N); int res = 1; while (i >= 1) { // If i is a factor of N if (N % i == 0) { if (i >= minSum) res = Math.max(res, N / i); if (N / i >= minSum) res = Math.max(res, i); } i--; } return res; } // Driver code public static void main (String[] args) { int N = 18, K = 3; System.out.println(maxGCD(N, K)); }}// This code is contributed by ApurvaRaj |
Python
# Python3 implementation of the approachfrom math import sqrt,ceil,floor# Function to calculate maximum GCDdef maxGCD(N, K): # Minimum possible sum for # K unique positive integers minSum = (K * (K + 1)) / 2 # It is not possible to divide # N into K unique parts if (N < minSum): return -1 # All the factors greater than sqrt(N) # are complementary of the factors less # than sqrt(N) i = ceil(sqrt(N)) res = 1 while (i >= 1): # If i is a factor of N if (N % i == 0): if (i >= minSum): res = max(res, N / i) if (N / i >= minSum): res = max(res, i) i-=1 return res# Driver codeN = 18K = 3print(maxGCD(N, K))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;class GFG{ // Function to calculate maximum GCD static int maxGCD(int N, int K) { // Minimum possible sum for // K unique positive integers int minSum = (K * (K + 1)) / 2; // It is not possible to divide // N into K unique parts if (N < minSum) return -1; // All the factors greater than sqrt(N) // are complementary of the factors less // than sqrt(N) int i = (int) Math.Sqrt(N); int res = 1; while (i >= 1) { // If i is a factor of N if (N % i == 0) { if (i >= minSum) res = Math.Max(res, N / i); if (N / i >= minSum) res = Math.Max(res, i); } i--; } return res; } // Driver code public static void Main() { int N = 18, K = 3; Console.WriteLine(maxGCD(N, K)); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// javascript implementation of the approach // Function to calculate maximum GCD function maxGCD(N , K) { // Minimum possible sum for // K unique positive integers var minSum = (K * (K + 1)) / 2; // It is not possible to divide // N into K unique parts if (N < minSum) return -1; // All the factors greater than sqrt(N) // are complementary of the factors less // than sqrt(N) var i = parseInt( Math.sqrt(N)); var res = 1; while (i >= 1) { // If i is a factor of N if (N % i == 0) { if (i >= minSum) res = Math.max(res, N / i); if (N / i >= minSum) res = Math.max(res, i); } i--; } return res; } // Driver code var N = 18, K = 3; document.write(maxGCD(N, K));// This code contributed by Rajput-Ji </script> |
3
Time Complexity: O(N1/2)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
