Loading...
Loading...
Loading...
A group of friends shares a running UPI ledger. Each of n entries is the net amount for one day: positive when money came in, negative when it went out.
They can split a stretch of days evenly among k people only when the stretch total is divisible by k. Count the stretches of one or more consecutive days whose total is divisible by k. A total of 0 or a negative multiple of k also counts.
Example 1
Input
6 5 4 5 0 -2 -3 1
Output
7
Seven stretches work, for example 5, then 5 0, and 5 0 -2 -3 with a total of 0.
Example 2
Input
2 5 4 -5
Output
1
Day 2 alone has total −5, which is divisible by 5.
Try the problem first. Open one hint at a time.
A stretch total is (running total at the end) − (running total just before the start).
That difference is divisible by k exactly when both running totals leave the same remainder when divided by k.
Count remainders in a HashMap as you go, starting with remainder 0 seen once.
In Java, -1 % 5 is -1, not 4. Turn every remainder into the range 0 to k − 1 with ((x % k) + k) % k.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor