Problem Link - Exam Cheating in Number theory
Problem Statement:
This problem asks us to find out how many values of p (the number of different sets of exam questions) will allow Ram and Shyam to cheat by getting the same set of questions.
Approach:
- Assignment Rule: The student with roll number r receives set number (r−1)%p.
- Objective: Ram and Shyam can only cheat if they receive the same set. This means that: (A−1)%p = (B−1)%p. A is Ram’s roll number and B is Shyam’s roll number.
- Condition Simplification: We can simplify the equation:
(A−1)%p = (B−1)%p ⇒ (A−B)%p = 0. Thus, p must divide (A−B). Now we have to find the divisors of (A-B), because p must be one of those divisors.
Now there are two scenarios:- When A=B: In this case, (A-B)=0 and p can be any value. Thus, there are infinitely many values of p, so result is -1.
- When A≠B: In this case, the number of valid values for p is equal to the number of divisors of |A-B|
- Find Divisors: The approach to counting divisors of a number n is based on the fact that divisors come in pairs. For every divisor i of n, there exists a corresponding divisor \frac{n}{i} . By iterating only up to \sqrt{n} , we efficiently find all divisors, as any divisor greater than \sqrt{n} would have already been paired with a divisor smaller than \sqrt{n} .
Complexity:
- Time Complexity: O(\sqrt{A-B} ) We are iterating through \sqrt{A-B} to find the divisors.
- Space Complexity:
O(1)No extra space is required.