A Stretch Divisible by k

Medium

You are given an array of non-negative integers values and a positive integer divisor. Check whether the array contains a contiguous stretch of **at least two** elements whose sum is divisible by divisor. Zero counts as divisible by anything. Return True if such a stretch exists and False otherwise.

Example 1

values=[5, 3, 8, 1], divisor=4 → True

The stretch [5, 3] sums to 8, which is divisible by 4.

Example 2

values=[7, 7], divisor=5 → False

The only candidate is the whole array with sum 14, which is not divisible by 5. A single number does not count.

Example 3

values=[4, 0, 0], divisor=9 → True

The two zeros in a row sum to 0, and 0 is divisible by anything.

Constraints

1 ≤ len(values) ≤ 10⁵
0 ≤ values[i] ≤ 10⁹
sum(values) ≤ 2³¹ − 1
1 ≤ divisor ≤ 2³¹ − 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Math Prefix Sum

Similar problems

Stretches With k Odd Numbers Medium Split Into Equal-XOR Halves Medium Pair GCDs by Sorted Position Hard Longest Run with a Given Sum Medium Vertical Mirror Line Medium

Input

values=[5, 3, 8, 1], divisor=4

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 118 tests on the server, hidden ones included.