### qhung312's blog

By qhung312, history, 5 months ago,

1345C - Hilbert's Hotel requires you to check if all (i + arr[i]) % n is distinct, so I did:

for (int i = 0; i < n; i++) {
ll x;
cin >> x;
arr[i] = (i + x) % n;
s.insert(arr[i]);
}
cout << ((s.size() == n) ? "YES" : "NO") << '\n';


This got WA on test 2, whereas if I change it to:

arr[i] = ((i + x) % n + n) % n;


This got AC. But aren't (i + x) % n and ((i + x) % n + n) % n the same thing?

• +9

 » 5 months ago, # |   0 Auto comment: topic has been updated by qhung312 (previous revision, new revision, compare).
 » 5 months ago, # |   +10 You need to handle the case when $i$ $+$ $a[i]$ is negative.
 » 5 months ago, # |   +9 (i+x) can be negative and C++ will give negative remainder.((i + x) % n + n) % n here you are changing the negative remainder to positive.If i + x is positive then (i + x) % n = ((i + x) % n + n) % nTry running this in c++ cout << (-8)%5 << " " << ((-8)%5+5)%5 << "\n"; cout << (8)%5 << " " << ((8)%5+5)%5; 
 » 5 months ago, # | ← Rev. 2 →   +9 For a positive a[i] : yes, both are same.(in this problem a[i]=i+a[i]) But when a[i]<0 : -(n-1) <= a[i]%n <=0, to brimg this value in between [0,n) we add +n to this value and take the modulus again to make it lie in the said range. Ex : -8%5=2 as -8 is 2 ahead of multiple of 5(i.e. -10) but modulus operator will compute this value to be -3, so we add +5 to this and take % with 5 again to get the correct answer!
•  » » 5 months ago, # ^ |   +1 Thanks. I didn't know the % operator behaved like that for negative numbers, so I was expecting a positive result every time.
 » 5 months ago, # |   -8 Because (0-1)%3 equals to -1, so you need to add n.