Given three integers N, R and P where P is prime, the task is to find whether NCR is divisible by P or not.
Examples:
Input: N = 6, R = 2, P = 7
Output: No
6C2 = 15 which is not divisible by 7.
Input: N = 7, R = 2, P = 3
Output: Yes
7C2 = 21 which is divisible by 3.
Approach: We know that NCR = 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 NCR 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 intusing namespace std;// Function to return the highest// power of p that divides n!// implementing Legendre Formulaint 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 pbool 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 codeint 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 approachimport 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 pstatic 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 approachusing 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(logpn)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
