Given a and b, find m such that a mod m = b mod m

1
votes

I am trying to solve a algorithmic problem, which has a sub-part which asks you to find an integer m such that for given two integers a and b, we get a mod m = b mod m. mod is the modulo operation. How to approach this problem?

3
algorithmmathmodulo
Will any choice of m do, or are you looking for the largest possible choice of m? – templatetypedef
This question appears to be off-topic because it is not a programming question as defined in the help center guidelines. – Ken White

3 Answers

7
votes
          a mod m = b mod m
==> (a - b) mod m = 0 
==>         (a-b) = k * m    for some integer k
==>     (a-b) / m = k

So m can be any factor of a-b .

1
votes

we have to find any number such that A % M == B % M now to satisfy this condition

  1. we can assume without loss of generality A > B then B = A - (A - B)
  2. now we take mod on both sides it will become B % M = (A - (A - B)) % M
  3. to reduce (A-B) from our equation we can replace M with (A-B)
  4. our equation become B % (A-B) = (A - (A-B)) % (A-B) solving it futher it becomes B % (A-B) = (A % (A-B) - (A-B) % (A-B)) as (A-B) % (A-B) is 0
  5. so our final equation will becomes B % (A - B) = A % (A - B) which is same as given equation here M = (A - B) is our final answer
M = (A - B) if A > B 
M = (B - A) if B > A
0
votes

for greatest possible m

public int solve(int A, int B) {
   
   
    if(A>B){
        return A-B;
    }
        return B-A;

    }

**Runtime estimation 1433ms **