Knowee
Questions
Features
Study Tools

You are given two integers 'n' and 'r' and a prime number 'p'. Your task is to find (nCr) % p where nCr can be calculated as n! / (r! * (n - r)!).Note :N! = 1 * 2 * 3 *... NInput format :The first line of input contains a single integer 'T', representing the number of test cases. The first line of each test case contains three space-separated integers 'n', 'r', and 'p'.Output format :For each test case, print a single line containing an integer representing the value of (nCr) % p.The output of each test case will be printed on a separate line.Note:You don't need to input or print anything, it has already been taken care of. Just implement the given function.Constraints :1 <= T <= 5 1 <= n, r, p <= 5 * 10 ^ 2p is prime number.Time limit: 1 sec.Sample Input 1 :2 5 2 114 3 13Sample Output 1 :104Explanation for Sample Output 1:In test case 1, n = 5, r = 2, and p = 11n C r = 5 C 2 = (5 * 4) / (2!) = 10n C r % p = 10 % 11 = 10. So the answer will be 10.In test case 2,n = 4, r = 3, and p = 13 n C r = 4 C 3 = 4 C 1 = 4 n C r % p = 4 % 13 = 4. So the answer will be 4.Sample Input 2 :25 2 1710 2 13Sample Output 2 :106

Question

You are given two integers 'n' and 'r' and a prime number 'p'. Your task is to find (nCr) % p where nCr can be calculated as n! / (r! * (n - r)!).Note :N! = 1 * 2 * 3 *... NInput format :The first line of input contains a single integer 'T', representing the number of test cases. The first line of each test case contains three space-separated integers 'n', 'r', and 'p'.Output format :For each test case, print a single line containing an integer representing the value of (nCr) % p.The output of each test case will be printed on a separate line.Note:You don't need to input or print anything, it has already been taken care of. Just implement the given function.Constraints :1 <= T <= 5 1 <= n, r, p <= 5 * 10 ^ 2p is prime number.Time limit: 1 sec.Sample Input 1 :2 5 2 114 3 13Sample Output 1 :104Explanation for Sample Output 1:In test case 1, n = 5, r = 2, and p = 11n C r = 5 C 2 = (5 * 4) / (2!) = 10n C r % p = 10 % 11 = 10. So the answer will be 10.In test case 2,n = 4, r = 3, and p = 13 n C r = 4 C 3 = 4 C 1 = 4 n C r % p = 4 % 13 = 4. So the answer will be 4.Sample Input 2 :25 2 1710 2 13Sample Output 2 :106

...expand
🧐 Not the exact question you are looking for?Go ask a question

Solution

The problem is asking to calculate the value of (nCr) % p for given 'n', 'r', and 'p' where 'p' is a prime number. nCr is a combination formula which can be calculated as n! / (r! * (n - r)!).

Here are the steps to solve this problem:

  1. First, we need to calculate the factorial of 'n', 'r', and 'n-r'. Factorial of a number is the product of all positive integers less than or equal to that number. For example, factorial of 5 (denoted as 5!) is 12345 = 120.

  2. After calculating the factorials, we can calculate the value of nCr by dividing the factorial of 'n' by the product of the factorials of 'r' and 'n-r'.

  3. Once we have the value of nCr, we can find the modulus of nCr with 'p' (nCr % p). The modulus operation finds the remainder after division of one number by another (sometimes called modulus).

  4. Repeat the steps for each test case.

  5. Return or print the result for each test case.

Note: As the constraints are high, the above approach may not work due to integer overflow (as factorials of numbers are generally large). So, we need to use some efficient algorithm to calculate nCr % p. One such algorithm is Lucas's Theorem which is used to compute the value of nCr % p efficiently when 'p' is a prime number.

This problem has been solved

Similar Questions

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.OutputFor every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.ExampleInput:21 103 5Output:235735

Write a program to count the number of prime factors of a given positive integer and calculate the difference between the number and the lowest prime factor.ExampleInput: 30 Output: 3 28Explanation: The number of prime factors is 3 (prime factors of 30 are 2, 3, and 5). The difference between the number (30) and the lowest prime factor (2) is 28.Note: This question was asked in the Wipro coding test.Input format :The input consists of an integer N, representing the positive integer.Output format :The output displays the count of prime factors and the difference between the given number and the lowest prime factor separated by a space.

Write a program to calculate the factorial of N.

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!InputThe input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.OutputFor every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.ExampleInput:21 103 5Output:235735Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed)InformationAfter cluster change, please consider PRINT as a more challenging problem.

Given two numbers N and R, find the value of NCR.Input FormatThe first and only line of input contains integers N and R.Output FormatPrint the value of NCRConstraints1 <= N <= 101 <= R <= 10ExampleInput5 3Output10

1/2

Upgrade your grade with Knowee

Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.