kazama460's blog

Need help in Modular Arithmetic (Simple Problem)
By kazama460, history, 6 years ago, In English

i am stuck at simple problem , and the problem is that there is no Editorial available for this problem.

The problem is as follows:

Given M (Distinct) integers A1 , A2 , A3 , A4 , A5 ...... , Am , find all integers K , such that remainder of all elements with k is same I.E. A1%K = A2%K = A3%K = ..... = Am%K

and K>1.

Number of elements are 100 , and Ai <= 10^9

My solution is brute force: i am running a loop from 2 to second largest element (which can be upto 10^9) and finding all k , but its giving TLE.

This is the link to the problem

any hint or help would be appreciative. Thanks in advance and happy coding.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

ghoshsai5000 has written a succinct explanation here.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Hey ! Thank you so much for citing me ! I didn't know anybody other than me checks my GitHub !

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      and thanks ghoshsai5000 for writing such a good explaination , i hope you keep up your good work.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hope it was helpful to you. If you get stuck again, you can consult my GitHub or Quora :)

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          of course i will if i am stuck at some point

          → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks pleasant for pointing out this link.

    → Reply