Co-prime or mutually prime pairs are those pairs of numbers whose GCD is 1. Given a number n represent the number as the sum of a Co-prime pair (A, B) such that A – B is minimum.
Examples :
Input : 12 Output : 5 7 Possible co-prime pairs are (5, 7), (1, 11) but difference between 5 and 7 is minimum Input : 13 Output : 6 7 Possible co-prime pairs are (6, 7), (5, 8), (4, 9), (3, 10), (2, 11) and (1, 12) but difference between 6 and 7 is minimum
A simple solution is to iterate through all numbers from 1 to n-1. For every number x, check if n – x and x are co-primes. If yes, then update the result if the difference between these two is less than the minimum difference so far.
An efficient solution is based on the fact that the numbers with a minimum difference should be close to n/2. We loop from n/2 to 1. Check every possible pair and when the first possible Co-prime pair is found display it and stop the loop.
C++
// CPP program to represent a number // as sum of a co-prime pair such that // difference between them is minimum #include <bits/stdc++.h> using namespace std; // function to check if pair // is co-prime or not bool coprime(int a, int b) { return (__gcd(a, b) == 1); } // function to find and print // co-prime pair void pairSum(int n){ int mid = n / 2; for (int i = mid; i >= 1; i--) { if (coprime(i, n - i) == 1) { cout << i << " " << n - i; break; } } } // driver code int main() { int n = 11; pairSum(n); return 0; } |
Java
// Java program to represent a // number as sum of a co-prime // pair such that difference // between them is minimum import java.io.*; public class GFG { static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // function to check if pair // is co-prime or not static boolean coprime(int a, int b) { return (__gcd(a, b) == 1); } // function to find and // print co-prime pair static void pairSum(int n) { int mid = n / 2; for (int i = mid; i >= 1; i--) { if (coprime(i, n - i) == true) { System.out.print( i + " " + (n - i)); break; } } } // Driver Code public static void main(String args[]) { int n = 11; pairSum(n); } } // This code is contributed by Sam007 |
Python3
# Python3 program to represent # a number as sum of a co-prime # pair such that difference # between them is minimum import math # function to check if pair # is co-prime or not def coprime(a, b): return 1 if(math.gcd(a, b) == 1) else 0; # function to # find and print # co-prime pair def pairSum(n): mid = int(n / 2); i = mid; while(i >= 1): if (coprime(i, n - i) == 1): print(i, n - i); break; i = i - 1; # Driver code n = 11; pairSum(n); # This code is contributed # by mits |
C#
// C# program to represent a number // as sum of a co-prime pair such that // difference between them is minimum using System; class GFG { static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // function to check if pair // is co-prime or not static bool coprime(int a, int b) { return (__gcd(a, b) == 1); } // function to find and print // co-prime pair static void pairSum(int n) { int mid = n / 2; for (int i = mid; i >= 1; i--) { if (coprime(i, n - i) == true) { Console.Write( i + " " + (n - i)); break; } } } // Driver code public static void Main() { int n = 11; pairSum(n); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to represent // a number as sum of a // co-prime pair such that // difference between them // is minimum function gcd($num1, $num2) { /* finds the greatest common factor between two numbers */while ($num2 != 0) { $t = $num1 % $num2; $num1 = $num2; $num2 = $t; } return $num1; } // function to check if pair // is co-prime or not function coprime($a, $b) { if(gcd($a, $b) == 1) return 1; else return 0; } // function to find and // print co-prime pair function pairSum($n) { $mid = (int)(($n / 2)); for ($i = $mid; $i >= 1; $i--) { if (coprime($i, $n - $i) == 1) { echo $i . " " . ($n - $i); break; } } } // Driver code $n = 11; pairSum($n); // This code is contributed // by mits ?> |
Javascript
<script> // Javascript program to represent a // number as sum of a co-prime // pair such that difference // between them is minimum function __gcd(a, b) { return b == 0 ? a : __gcd(b, a % b); } // function to check if pair // is co-prime or not function coprime(a, b) { return (__gcd(a, b) == 1); } // function to find and // print co-prime pair function pairSum(n) { let mid = Math.floor(n / 2); for (let i = mid; i >= 1; i--) { if (coprime(i, n - i) == true) { document.write( i + " " + (n - i)); break; } } } // Driver code let n = 11; pairSum(n); </script> |
Output
5 6
Time Complexity: O(n*log(n))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
