Modulo product ninja got an easy assignment from his professor but he is unable to solve this. So he needs your help to complete the assignment.

Question

1.00/5 (2 votes)

See more:

Modulo product
Ninja got an easy assignment from his professor but he is unable to solve this. So he needs your help to complete the assignment.
In the assignment, he is given two integers A and B and he needs to output the product of all numbers from 1 to A modulo B, where 1 and A are inclusive.
For example, if A=5 and B=7, the answer will be ( 1 * 2 * 3 * 4 * 5 ) % 7 = 1 so the final answer is 1.
Input format:
The first line of input will contain an integer T, that denote the number of test cases.
Every test case will consist of one single line and that line will contain two integers: A and B.
Constraints:
1<=T<=50
1<=A<=10^9
1<=B<=10^5
Time Limit: 1 second
Output format:
For every test case, print the output in a newline.
Sample Input 1
4
8 10
5 140
18 19
20 21
Sample Output 1:
0
120
18
0

What I have tried:

Java

import java.util.Scanner;

public class ModuloProduct {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt(); // number of test cases
        
        while (t > 0) {
            int a = scanner.nextInt(); // value of A
            int b = scanner.nextInt(); // value of B
            
            int result = moduloProduct(a, b);
            System.out.println(result);
            
            t--;
        }
        
        scanner.close();
    }
    
    private static int moduloProduct(int a, int b) {
        int product = 1;
        
        // Calculate the product of all numbers from 1 to A
        for (int i = 1; i <= a; i++) {
            product = (product * i) % b;
        }
        
        return product;
    }
}

Posted 18-Jul-23 4:38am

Hari Suman

Updated 19-Jul-23 21:48pm

Andre Oosthuizen

v2

Add a Solution

Comments

Patrice T 18-Jul-23 14:44pm

And you plan to tell us what is your problem ?

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CPallini · Answer 1 · 2023-07-18T20:34:00

Solution 2

Your program is correct (at least it produces the expected output from the sample input).
So, what is your doubt about?

Posted 18-Jul-23 20:34pm

CPallini

Richard MacCutchan · Answer 2 · 2023-07-18T04:49:00

Solution 1

I think this part is incorrect*:

Java

for (int i = 1; i <= a; i++) { product = (product * i) % b; } return product;

Try:

Java

for (int i = 1; i <= a; i++) { product = product * i; } return product % b;

* although that depends on how you read the phrase, "the product of all numbers from 1 to A modulo B".

Posted 18-Jul-23 4:49am

Richard MacCutchan

Updated 18-Jul-23 21:55pm

v2

Comments

CPallini 19-Jul-23 2:38am

Fortunately the two pieces of code produce the same result, so you may use the first one in order to avoid dealing with huge numbers (a!).

Richard MacCutchan 19-Jul-23 3:28am

I (obviously) didn't think of that. :)

KarstenK · Answer 3 · 2023-07-19T21:48:00

Solution 3

You need to divide the modulo product after all multiplication is done and NOT in every loop.

Java

private static int moduloProduct(int a, int b) {
        int product = 1;
        
        // Calculate the product of all numbers from 1 to A
        for (int i = 1; i <= a; i++) {
            //product = (product * i) % b;
            product = (product * i);
        }
        
        return product/b;
    }

BTW: use better naming like and check the modulo for 0. It could crash without checke.

Java

private static int moduloProduct(int producto, int modulo)

Posted 19-Jul-23 21:48pm

KarstenK

Comments

CPallini 20-Jul-23 3:55am

Actually you usually cannot perform all the multiplications before applying the modulo (because factorial becomes soon very large). Applying the modulo at each iteration produces the correct result.
Note, your code is returning the quotient, not the reminder.

Richard MacCutchan 20-Jul-23 4:23am

As Carlo already pointed out to me, the original code is correct. I tested with both options and soon got overflowed values when leaving the modulo function to the end.