0
\$\begingroup\$

I was asked this question in an interview.

You are given an array consisting of N integers. You need to determine whether any permutation of a given array exists such that the sum of all subarrays of length K are equal. N is divisible by K i.e. N mod K = 0.
If the array is [1,2,1,3,2,3] and K = 2, it is False.
If the array is [1,2,1,3,2,3] and K = 3, it is True.

My logic was this.

  1. If N == K, return True.
  2. Else store each of the distinct element in the array in a dictionary. If the number of distinct elements in the dictionary is greater than K, return False.
  3. Else store the count of each distinct element in the dictionary.
  4. If the count of any distinct element is less than (N/K), return False.
  5. Finally return True.

Here is my code in Python:

def check(nums, n, k):
if n == k:
    return True
else:
    my_dict = {}
    for i in nums:
        if i not in my_dict:
            my_dict[i] = 1
        else:
            my_dict[i] += 1
    if len(my_dict) > k:
        return False
    count = int(n/k)
    for i,j in my_dict.items():
        if j < count:
            return False
    return True  

Am I doing the right approach ?

\$\endgroup\$
  • \$\begingroup\$ How about [1, 2, 3, 4], and K = 2? \$\endgroup\$ – vnp Sep 9 '18 at 16:09
  • \$\begingroup\$ It will return False. All the possible subarrays (including the permutations of the given array) of length 2 are [1,2], [1,3], [1,4], [2,3], [2,4] and [3,4]. We can see that the sum of each of these subarrays are not equal. \$\endgroup\$ – Abascus Sep 9 '18 at 19:37
  • \$\begingroup\$ @GarethRees Sir, in your example N = 8 and K = 3. This input will be invalid since 8 mod 3 != 0. \$\endgroup\$ – Abascus Sep 10 '18 at 8:15
  • \$\begingroup\$ Define subarray. Is it a contiguous set (e.g. for ABCDE, the only valid subarrays (K=3) are ABC, BCD and CDE) or non-contiguous (e.g. ACD is also considered a subarray)? No matter what definition you use, I cannot make heard or tails of your true/false examples. Can you show us a specific (exhaustive) list of all subarrays from a given example; and an explanation why this is true/false? \$\endgroup\$ – Flater Oct 10 '18 at 13:26
1
\$\begingroup\$

Use the collections.Counter instead of keeping a count yourself.

When you have counted all the elements from the list, check if any of their counts is not a factor of \$ N \$ and return False.

Therefore:

from collections import Counter

def check(nums, n, k):
    if n == k:
        return True
    counts = Counter(nums)
    if len(counts) > k:
        return False
    return all((n % x == 0 for x in counts.values()))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.