Loading...
Loading...
Loading...
A student checks her UPI history. Each entry is an amount in rupees: money received is positive, money paid is negative.
She has n entries and a number k. Count the pairs of entries (i, j) with i < j whose amounts add up to a multiple of k. Zero counts as a multiple of k.
Example 1
Input
6 5 2 3 7 8 10 5
Output
5
The pairs are (2, 3), (2, 8), (3, 7), (7, 8) and (10, 5).
Example 2
Input
3 4 -1 5 3
Output
2
−1 + 5 = 4 and 5 + 3 = 8 are multiples of 4, but −1 + 3 = 2 is not.
Try the problem first. Open one hint at a time.
Whether a + b is a multiple of k depends only on the remainders of a and b when divided by k.
If a has remainder r, its partner needs remainder (k − r) % k. Remainder 0 pairs with remainder 0.
Walk through the list once. For each amount, add the number of earlier amounts with the partner remainder, then record this amount's remainder.
In Java, -3 % 5 is −3. Use ((a % k) + k) % k to get a remainder from 0 to k − 1. The count can be near 5 × 10^9, so use long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor