Cocubes Coding | Co-prime pairs in array

In this blog we are discussing a cocubes coding question to count the number of co-prime pairs in an array.

Now by co-prime we mean that any two numbers whose GCD is 1 are be called as co-prime.


Input:

The first line contains an integer T, total number of elements. Then follow T elements.

3
1 2 3

Output:

Count the number of co-prime pairs in an array

3

Here, Co-prime pairs are (1, 2), (2, 3), (1, 3)


Constraints:

1 <= T <= 25
1 <= elements <= 100

Implementation using C:

#include <stdio.h>
int co_prime(int a, int b)
{
    int gcd;
    while( a!=0 )
    {   gcd = a;
        a = b%a;
        b = gcd; 
    }
    if(gcd == 1)
        return 1;
    else
        return 0;
}

int count_pairs(int arr[], int n)
{
    int count = 0;
    for(int i = 0; i < n-1; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(co_prime(arr[i], arr[j]))
                count++;
        }
    }
    return count;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    int a[25], i;
    for(i = 0; i < n; i++)
        scanf("%d", &a[i]);
    printf("%d", count_pairs(a, n));
    
    return 0;
}

Happy Coding!

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor


Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #learn #computer #science

49 views1 comment

        Contact Us

programmersdoor@gmail.com

  • LinkedIn
  • Facebook
  • Instagram

©2023 by Programmers Door