Keep an array of the frequencies of ((x % k) + k) % k for each x in arr.

for each i in [0, k - 1] we need to check if freq[i] == freq[k - i]

Take care of the case when i == k - i and when i == 0