HackerEarth Coprimes problem solution

YASH PAL, 31 July 202416 February 2026

In this HackerEarth Coprimes problem solution, You are provided an integer n. Your task is to determine the largest integer a (a < n – 1) that is coprime of n. This implies that gcd(a,n) = 1.

HackerEarth Coprimes problem solution

HackerEarth Coprimes problem solution.

#include <bits/stdc++.h>

typedef long double ld ;
#define long long long int
using namespace std;
#define mp make_pair
#define pb push_back
#define x first
#define y second
typedef pair<long,long> pll; 

const int N=1e5+1;

long GCD(long a,long b)
{
    while(a && b)
    {
        a=a%b;
        if(a)
            b=b%a;
    }
    return a+b;
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    srand(time(NULL));

    int t=1;
    while(t--)
    {
        long n;
        cin>>n;
        assert(3<=n && n<=1e18);

        if(n&1)
            cout<<n-2<<"n";
        else
        {
            long temp=2;
            while(true)
            {
                long temp_gcd=GCD(n,n-temp);
                if(temp_gcd==1)
                {
                    cout<<n-temp<<"n";
                    break;
                }
                temp++;
            }
        }

    }

    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 17;
 
ll n;
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    if(n % 2 == 0){
        for(int i = n - 3; ; i -= 2)
            if(gcd(n, i) == 1){
                cout << i << 'n';
                break;
            }
    }
    else
        cout << n - 2 << 'n';
}

coding problems solutions HackerEarth HackerEarth

Leave a Reply