Split given number into two distinct numbers having GCD 1
Given an Integer as N, the task is to convert N into two numbers a and b, such that a < b and GCD(a, b) is equal to 1.
Examples:
Input: N = 12
Output: 5 7Input: N = 9
Output: 4 5
Approach: The idea is to start iterating from the back of the loop starting from the number itself. Follow the steps given below to solve the problem.
- If N is less than equal to 2, the answer doesn’t exist.
- Otherwise iterate over the range [N/2, 0) using the variable i and perform the following tasks:
- If the gcd of i and N-i is 1 then print this as the answer and return.
Below is the implementation of the above approach:
C++
/// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to split N into two numbers void find( int n) { // Base Case if (n <= 2) { cout << "-1" ; } else { // Since a < b // start from n/2 for ( int i = n / 2; i > 0; i--) { // Sum of a and b is n int a = i, b = n - i; // Check the gcd if (__gcd(a, b) == 1 && a < b) { cout << a << ", " << b; return ; } } } } // Driver Code int main() { int N = 9; find(N); return 0; } |
Java
/// Java program for the above approach class GFG { // Function to split N into two numbers public static void find( int n) { // Base Case if (n <= 2 ) { System.out.println( "-1" ); } else { // Since a < b // start from n/2 for ( int i = n / 2 ; i > 0 ; i--) { // Sum of a and b is n int a = i, b = n - i; // Check the gcd if (__gcd(a, b) == 1 && a < b) { System.out.println(a + ", " + b); return ; } } } } static int __gcd( int a, int b) { if (b == 0 ) return a; return __gcd(b, a % b); } // Driver Code public static void main(String args[]) { int N = 9 ; find(N); } } // This code is contributed by saurabh_jaiswal. |
Python3
# Python 3 program for the above approach import math # Function to split N into two numbers def find(n): # Base Case if (n < = 2 ): print ( "-1" ) else : # Since a < b # start from n/2 for i in range (n / / 2 , - 1 , - 1 ): # Sum of a and b is n a = i b = n - i # Check the gcd if (math.gcd(a, b) = = 1 and a < b): print (a, "," , b) return # Driver Code if __name__ = = "__main__" : N = 9 find(N) #vThis code is contributed by ukasp. |
C#
/// C# program for the above approach using System; public class GFG { // Function to split N into two numbers public static void find( int n) { // Base Case if (n <= 2) { Console.WriteLine( "-1" ); } else { // Since a < b // start from n/2 for ( int i = n / 2; i > 0; i--) { // Sum of a and b is n int a = i, b = n - i; // Check the gcd if (__gcd(a, b) == 1 && a < b) { Console.WriteLine(a + ", " + b); return ; } } } } static int __gcd( int a, int b) { if (b == 0) return a; return __gcd(b, a % b); } // Driver Code public static void Main(String []args) { int N = 9; find(N); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript code for the above approach // Recursive function to return gcd of a and b function __gcd(a, b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to split N into two numbers function find(n) { // Base Case if (n <= 2) { document.write( "-1" ); } else { // Since a < b // start from n/2 for (let i = Math.floor(n / 2); i > 0; i--) { // Sum of a and b is n let a = i, b = n - i; // Check the gcd if (__gcd(a, b) == 1 && a < b) { document.write(a + ", " + b); return ; } } } } // Driver Code let N = 9; find(N); // This code is contributed by Potta Lokesh </script> |
Output
4, 5
Time complexity: O(N log(N))
Auxiliary space: O(1)
Contact Us