The Hitmen twins of the Juarez Cartel, Leonel and Marco Salamanca, often known as the “Cousins”

Question

The Hitmen twins of the Juarez Cartel, Leonel and Marco Salamanca, often known as the “Cousins” have a set off from Mexican in search of Walter white. They come across an informant, who only agrees to help them if they solve his puzzle of interesting numbers.

There are N interesting numbers A1, A2,….An, consisting of integers from 1 to N.

The task is to find Kth smallest GCD among all GCD(Ai…Aj) for each (I,j).

Such that 1 ≤ I < j ≤N.

Print the Kth smallest GCD and also find any pair having the resultant GCD

(Print their indices).

Input:

1

5 7

2 4 4 1 3

Output:

1

1 4

Summary

In the below program, we have taken test cases of number t. Each time for the test case two variables ‘n’ and ‘k’ are taken. For loop is used to having an array. Next for loop is used to find the GCD of every possible ordered pair. So Next we again use for loop to sort the GCD obtained in ascending order using the bubble sort technique. Then we print the Kth smallest GCD. Then we print the pair with the Kth smallest GCD.

Explanation

In this program, we have to use the t variable for the number of test cases. In the while loop, we declare two variables ‘n’ and ‘k’  and have taken its array by for loop, and name ‘c’ is given to array. So For loop starting from 0 is passed to another loop where every pair is forward to GCD function and is move in the g[] array. So GCD found of the two integers are save in the array p[] and q[]. Then array g[],p[] and q[] will be sort in ascending order using the bubble sort technique. After that ‘k’ smallest GCD will get print on the screen.

Code

#include <iostream>
using namespace std;
/* to find the gcd of two numbers */
int gcd(int c,int d)
{
    /* if any of the numbers is zero */
    if(c==0)
    return d;
    else if(d==0)
    return c;
    /* otherwise */
    else if(c>d)
    return gcd(d,c%d);
    else 
    return gcd(c,d%c);
}
int main()
{
    /* to have number of test cases */
    int t;
    cin>>t;
    while(t--)
    {
        /* to enter the valve of n and k*/
        int n,k;
        cin>>n>>k;
        int c[n];
        /* array */
        for(int i=0;i<n;i++)
        cin>>c[i];
        int p[n*(n+1)],q[n*(n+1)];
        int g[n*(n+1)];
        int cc=0;
        /* to find the gcd of every possible ordered pair */
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                g[cc]=gcd(c[i],c[j]);
                p[cc]=c[i];
                q[cc]=c[j];
                cc++;
            }
        }
        /* to sort the gcds in ascending order  
        using the bubble sort technique */
        for(int i=0;i<cc;i++)
        {
            for(int j=0;j<cc-1-i;j++)
            {
                if(g[j]>g[j+1])
                {
                    int temp=g[j];
                    g[j]=g[j+1];
                    g[j+1]=temp;
                    int temp1=p[j];
                    p[j]=p[j+1];
                    p[j+1]=temp1;
                    int temp2=q[j];
                    q[j]=q[j+1];
                    q[j+1]=temp2;
                }
            }
        }
        /* to print the kth smallest gcd */
        cout<<g[k-1]<<endl;
        /* to print the pair with the kth smallest gcd */
        cout<<p[k-1]<<" "<<q[k-1]<<endl;
    }
}

Output

Also read, To select a laptop for an online class based on a budget below $400