Determine whether there exists a contiguous subarray of length > 1 with an integer mean

Admin 1
Viewed 665

Given an unsorted array of integers.

I'm trying to come up with an efficient solution (better than O(n2)) but the best I can come up with is an O(n2) solution:

for i from 0 to size of list:
    sum = list[i]

    for j from i + 1 to size of list:
        sum += list[j]

        if sum % (j - i + 1) == 0:
            return true
return false

I've read stuff on sliding window technique, but it looks like that would be useful for subarrays of a specific length k.

data-structures arrays algorithm
1 Answers

This might be a trick question :) Two odd numbers sum to an even number and two even numbers sum to an even number. The only data set that would not include a contiguous subarray of length two that's also divisible by two would have to alternate [..., odd, even, odd, even, ...]. But then the data set would need to be even further restricted to prevent a subarray of length 4 to be divisible by four, since every other even number is divisible by four.

The probability of receiving such a list is extremely small and continues to reduce as the list gets larger (what's more, it lends itself to a subset of numerical patterns; could those be of interest?), which means unless someone worked painstakingly to create some, most if not all real-world situations would find a solution with a sliding window of size 4 that also checks for alternating parity.

user_20347870
Related