How Many Sensor Rings Fit?
Medium About 30 min Free, no account needed
Count nonnegative sensor readings consistent with adjacent sums around a ring, without trying every possible first reading.
The brief
A ring of sensors lost its individual readings. The backup retained only the sum of each sensor's reading and the reading immediately clockwise from it. Several different sets of readings may produce the same backup.
Implement long Solve(int[] adjacentTotals). There are n sensors with unknown nonnegative integer readings x[0] through x[n - 1]. For every index i:
adjacentTotals[i] = x[i] + x[(i + 1) % n]Return the number of distinct reading arrays that satisfy every total. Sensor positions are fixed: rotations count as different arrays when they change any position. Return 0 if the backup is inconsistent.
For [3, 3, 3, 3], four arrays fit:
[0, 3, 0, 3]
[1, 2, 1, 2]
[2, 1, 2, 1]
[3, 0, 3, 0]For [5, 7, 6], only [2, 3, 4] fits, so return 1. For [1, 1, 1], return 0: the readings would have to be fractions.
There are between 1 and 200,000 sensors, and every total is between 0 and int.MaxValue. A one-sensor ring pairs that sensor with itself, so its total is twice its reading. A two-sensor ring records the same pair in both directions. The answer can exceed int.MaxValue; return a 64-bit integer and preserve the input array.
Starter code
using System;
public class Solution
{
public long Solve(int[] adjacentTotals)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Math and number theory
- Replace enumeration with a formula: GCD, modular arithmetic, digit math and closed-form counting.
Related katas
- Multiply Numeric Strings Medium Free Schoolbook multiplication of numbers thousands of digits long.
- Modular Exponentiation Medium Free Raise to a power of 10^18 - one squaring at a time.
- Subarrays Divisible by K Medium Free Count the subarrays whose sum is divisible by k.
- Sum of All Subarray Sums Medium Free Add up the sum of every contiguous subarray - without enumerating them.