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?
Auto comment: topic has been updated by qhung312 (previous revision, new revision, compare).
You need to handle the case when $$$i$$$ $$$+$$$ $$$a[i]$$$ is negative.
(i+x) can be negative and C++ will give negative remainder.
((i + x) % n + n) % nhere you are changing the negative remainder to positive.If
i + xis positive then(i + x) % n=((i + x) % n + n) % nTry running this in c++
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!
Thanks. I didn't know the
%operator behaved like that for negative numbers, so I was expecting a positive result every time.Because
(0-1)%3equals to -1, so you need to add n.