Find if nCr is divisible by the given prime

0 0 4 minutes read

Given three integers N, R and P where P is prime, the task is to find whether ^NC_R is divisible by P or not.
Examples:

Input: N = 6, R = 2, P = 7
Output: No
⁶C₂ = 15 which is not divisible by 7.
Input: N = 7, R = 2, P = 3
Output: Yes
⁷C₂ = 21 which is divisible by 3.

Approach: We know that ^NC_R = N! / (R! * (N – R)!). Now using Legendre Formula, find the largest power of P which divides any N!, R! and (N -R)! say x1, x2 and x3 respectively.
In order for ^NC_R to be divisible by P, the condition x1 > x2 + x3 must be satisfied.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
// Function to return the highest
// power of p that divides n!
// implementing Legendre Formula
int getfactor(int n, int p)
{
    int pw = 0;
 
    while (n) {
        n /= p;
        pw += n;
    }
 
    // Return the highest power of p
    // which divides n!
    return pw;
}
 
// Function that returns true
// if nCr is divisible by p
bool isDivisible(int n, int r, int p)
{
    // Find the highest powers of p
    // that divide n!, r! and (n - r)!
    int x1 = getfactor(n, p);
    int x2 = getfactor(r, p);
    int x3 = getfactor(n - r, p);
 
    // If nCr is divisible by p
    if (x1 > x2 + x3)
        return true;
 
    return false;
}
 
// Driver code
int main()
{
    int n = 7, r = 2, p = 7;
 
    if (isDivisible(n, r, p))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// Java Implementation of above approach
import java.io.*; 
 
class GFG 
{ 
 
// Function to return the highest 
// power of p that divides n! 
// implementing Legendre Formula 
static int getfactor(int n, int p) 
{ 
    int pw = 0; 
 
    while (n != 0) 
    { 
        n /= p; 
        pw += n; 
    } 
 
    // Return the highest power of p 
    // which divides n! 
    return pw; 
} 
 
// Function to return N digits 
// number which is divisible by p
static int isDivisible(int n, int r, int p) 
{ 
    // Find the highest powers of p 
    // that divide n!, r! and (n - r)! 
    int x1 = getfactor(n, p); 
    int x2 = getfactor(r, p); 
    int x3 = getfactor(n - r, p); 
 
    // If nCr is divisible by p 
    if (x1 > x2 + x3) 
        return 1; 
 
    return 0; 
} 
 
// Driver code 
public static void main (String[] args)
{ 
    int n = 7, r = 2, p = 7; 
 
    if (isDivisible(n, r, p) == 1) 
        System.out.print("Yes");
    else
        System.out.print("No");
 
} 
} 
 
// This code is contributed by krikti..

Python3

# Python3 implementation of the approach 
 
# Function to return the highest 
# power of p that divides n! 
# implementing Legendre Formula 
def getfactor(n, p) : 
 
    pw = 0; 
 
    while (n) : 
        n //= p; 
        pw += n; 
     
 
    # Return the highest power of p 
    # which divides n! 
    return pw; 
 
 
# Function that returns true 
# if nCr is divisible by p 
def isDivisible(n, r, p) :
     
    # Find the highest powers of p 
    # that divide n!, r! and (n - r)! 
    x1 = getfactor(n, p); 
    x2 = getfactor(r, p); 
    x3 = getfactor(n - r, p); 
 
    # If nCr is divisible by p 
    if (x1 > x2 + x3) :
        return True; 
 
    return False; 
 
 
# Driver code 
if __name__ == "__main__" :
     
    n = 7; r = 2; p = 7; 
 
    if (isDivisible(n, r, p)) : 
        print("Yes"); 
    else :
        print("No"); 
         
# This code is contributed by AnkitRai01

C#

// C# Implementation of above approach
using System;
 
class GFG
{
     
// Function to return the highest 
// power of p that divides n! 
// implementing Legendre Formula 
static int getfactor(int n, int p) 
{ 
    int pw = 0; 
 
    while (n != 0) 
    { 
        n /= p; 
        pw += n; 
    } 
 
    // Return the highest power of p 
    // which divides n! 
    return pw; 
} 
 
// Function to return N digits 
// number which is divisible by D 
static int isDivisible(int n, int r, int p) 
{ 
    // Find the highest powers of p 
    // that divide n!, r! and (n - r)! 
    int x1 = getfactor(n, p); 
    int x2 = getfactor(r, p); 
    int x3 = getfactor(n - r, p); 
 
    // If nCr is divisible by p 
    if (x1 > x2 + x3) 
        return 1; 
 
    return 0; 
} 
 
// Driver code 
static public void Main ()
{
    int n = 7, r = 2, p = 7; 
 
    if (isDivisible(n, r, p) == 1) 
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
 
} 
} 
 
// This code is contributed by ajit.

Javascript

<script>
    // Javascript Implementation of above approach
     
    // Function to return the highest 
    // power of p that divides n! 
    // implementing Legendre Formula 
    function getfactor(n, p) 
    { 
        let pw = 0; 
 
        while (n != 0) 
        { 
            n = parseInt(n / p, 10); 
            pw += n; 
        } 
 
        // Return the highest power of p 
        // which divides n! 
        return pw; 
    } 
 
    // Function to return N digits 
    // number which is divisible by D 
    function isDivisible(n, r, p) 
    { 
        // Find the highest powers of p 
        // that divide n!, r! and (n - r)! 
        let x1 = getfactor(n, p); 
        let x2 = getfactor(r, p); 
        let x3 = getfactor(n - r, p); 
 
        // If nCr is divisible by p 
        if (x1 > x2 + x3) 
            return 1; 
 
        return 0; 
    } 
     
    let n = 7, r = 2, p = 7; 
   
    if (isDivisible(n, r, p) == 1) 
        document.write("Yes");
    else
        document.write("No");
 
</script>

Output:

Yes

Time Complexity: O(log_pn)

Auxiliary Space: O(1)

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!