Co-prime pair with given sum minimum difference

0 0 4 minutes read

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)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!