Skip to content
Katabench
Try free

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:

Text
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:

Text
[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

C#
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.

C# coding challenges →

What it practices

Math and number theory
Replace enumeration with a formula: GCD, modular arithmetic, digit math and closed-form counting.

Related katas