Question

Amazon WoW | OA | SDE1 | Coding Questions and Solutions | 2022 | Set-45

Answer 1

Question asked : 

 

C++ code : 

// A modular inverse based solution to
// compute nCr % p
#include <bits/stdc++.h>
using namespace std;

/* Iterative Function to calculate (x^y)%p
in O(log y) */
unsigned long long power(unsigned long long x,
                                int y, int p)
{
    unsigned long long res = 1; // Initialize result

    x = x % p; // Update x if it is more than or
    // equal to p

    while (y > 0)
    {
    
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}

// Returns n^(-1) mod p
unsigned long long modInverse(unsigned long long n,
                                            int p)
{
    return power(n, p - 2, p);
}

// Returns nCr % p using Fermat's little
// theorem.
unsigned long long nCrModPFermat(unsigned long long n,
                                int r, int p)
{
    // If n<r, then nCr should return 0
    if (n < r)
        return 0;
    // Base case
    if (r == 0)
        return 1;

    // Fill factorial array so that we
    // can find all factorial of r, n
    // and n-r
    unsigned long long fac[n + 1];
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % p;

    return (fac[n] * modInverse(fac[r], p) % p
            * modInverse(fac[n - r], p) % p)
        % p;
}

// Driver program
int main()
{
    // p must be a prime greater than n.
    int n, r, p ;
    cin>>n>>r>>p ; 
    
    cout << "Value of nCr % p is "
        << nCrModPFermat(n, r, p);
    return 0;
}

Answer 2

Question asked : 

C++ code : 

// C++ program to count number of factors
// of an array of integers
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll ; 
const int MAX = 1000001;
ll dp[1000000+5];
// array to store prime factors
int factor[MAX] = { 0 };
vector <ll> G[MAX+5] ; 
// function to generate all prime factors
// of numbers from 1 to 10^6
void generatePrimeFactors()
{
    factor[1] = 1;

    // Initializes all the positions with their value.
    for (int i = 2; i < MAX; i++)
        factor[i] = i;

    // Initializes all multiples of 2 with 2
    for (int i = 4; i < MAX; i += 2)
        factor[i] = 2;

    // A modified version of Sieve of Eratosthenes to
    // store the smallest prime factor that divides
    // every number.
    for (int i = 3; i * i < MAX; i++) {
        // check if it has no prime factor.
        if (factor[i] == i) {
            // Initializes of j starting from i*i
            for (int j = i * i; j < MAX; j += i) {
                // if it has no prime factor before, then
                // stores the smallest prime divisor
                if (factor[j] == j)
                    factor[j] = i;
            }
        }
    }
}

// function to calculate number of factors
void calculateNoOfFactors(int n)
{
    int index = n ; 
    if (n == 1){
//        return 1;
}
    int ans = 1;

    // stores the smallest prime number
    // that divides n
    int dup = factor[n];
    //cout<<dup;
    //cout<<"\n";
    G[index].push_back(dup);
    // stores the count of number of times
    // a prime number divides n.
    int c = 1;

    // reduces to the next number after prime
    // factorization of n
    int j = n / factor[n];

    // false when prime factorization is done
    while (j != 1) {
        // if the same prime number is dividing n,
        // then we increase the count
        if (factor[j] == dup)
            c += 1;

        /* if its a new prime factor that is factorizing n,
        then we again set c=1 and change dup to the new
        prime factor, and apply the formula explained
        above. */
        else {
            dup = factor[j];
            //cout<<dup;
            //cout<<"\n";
            G[index].push_back(dup);
            ans = ans * (c + 1);
            c = 1;
        }

        // prime factorizes a number
        j = j / factor[j];
    }

    // for the last prime factor
    ans = ans * (c + 1);

    //return ans;
}

// Driver program to test above function
int main()
{

    generatePrimeFactors();
    dp[1] = 1 ; 
    dp[2] = 2 ; 
    
//     int a[] = {105};

//     int q = sizeof(a) / sizeof(a[0]);

//     for (int i = 0; i < q; i++){
//         cout << calculateNoOfFactors(a[i]) << " ";}
        
        
    ll i = 2 ; 
    while(i<=250000+55){
        
        calculateNoOfFactors(i);
        sort(G[i].begin(),G[i].end());
        i++;
    }
        
        
    i = 3 ; 
    while(i<=250000+55){
        ll oo = G[i].size();
        
        
        ll vv = G[i][oo-1];
        if(vv!=1 && vv!=i){
            dp[i] = 1 + min(dp[i-1],dp[vv]);
        }
        else
        {
            dp[i] = dp[i-1] + 1 ; 
        }
        
        
        i++;
    }
    ll n;
    cin>>n ; 
    cout<<dp[n] ; 
    return 0;
}