Divisible subsets

Problem statement

Given a multiset with n integers, find such a non-empty subset of it that the sum of the subset’s elements is divisible by N.

If many valid subsets are there, then print any.

Pre-requisites:

  • The pigeonhole principle
  • Subarrays

Problem explanation

Let’s look at the following example.

  • N=4

  • array = [4, 6, 10, 3]

Condition = the sum of the subset must be divisible by N (that is 4 in this example )

Some of the valid subsets are:

  • {4}

  • {6, 10}

Solution

We’ll prove that there will always exist a subarray of the array whose sum is divisible by N.

Let’s proceed with an example.

  • N = 5

  • array = [1, 2, 3, 5, 7]

We’ll first create a cumulative sum array, cumArray = [1, 3, 6, 11, 18]

Here, cumArray [i] represents the sum of subarray (0, i). We’ll change this cumArray to cumArray%N.

cumArray = [1, 3, 1, 1, 3]

Now, if any cumArray[ i ] == 0, this will mean that:

  • The sum of subarray (0, i)%N==0

  • Thus subarray found.

Else:

  • cumArray has N values.

  • Since we changed cumArray to cumArray%N, this means values in cumArray can only be in the range [0, N-1]. Which means there could be at max N different values in cumArray. But since we already checked there exists no 0 in cumArray, thus cumArray can now only have N-1 different value.

  • Now, According to the pigeonhole principle, at least 1 value in cumArray will occur twice.

  • This means there always will exist at least one (a,b) pair such that:

    • cumArray[ a]%N = cumArray[ b]%N

    • Therefore, the sum of subarray (a, b) is divisible by N.

    • Thus the subarray is found.

Hence, we proved that in either case, a subarray will exist with sum divisible by N.

Now, as we know it, we now do not need it to generate the whole cumArray first and then find the required subarray. We could simply find the required subarray whilst calculating the cumArray.

If x is the sum until ith index, then we just need to check if either x=0 or x occurred in cumArray previously. If yes, then we got the required subarray otherwise add x to cumArray and check for i+1th index.

Solution

Input

  • The first line of the input contains an integer T denoting the number of test cases.

  • The first line of each test consists of a single integer N which is the size of the multiset.

  • The second line of each test contains N space-separated integers which is the multiset’s elements.

Note. Press enter/ return key(↵) after each line, in order to input the next line.

Output

  • Print -1 if the required subset doesn’t exist.

  • Otherwise print two lines, first the size of the subset, then the space-separated indices of the subset.

Example

Input

  • 1
  • 5
  • 2 4 2 9 3

Output

  • 3
  • 2 3 4
t = int(input())
# t - test cases
for _ in range(t):
    N = int(input())
    # N - size of array
    array = list(map(int,input().split()))
    # array - array of N numbers.
    sumx = 0
    sumxIndex = {}
    
    for i in range(0,N):
        sumx = (sumx + array[i])%N
        
        if (sumx==0) :
            # sum of subarray [0,i] is divisible by N.  
            left = 0
            right = i
            break
        if (sumx in sumxIndex.keys()):
            # sum of subarray [prev index of sumx in sumIndex, i] is divisible by N
            left = sumxIndex[sumx]+1
            right = i
            break
        sumxIndex[sumx] = i
    
    
    print(right-left+1)
    
    for index in range(left,right+1):
        print(index+1,end=" ")
    print()

Enter the input below

Python Code

Code explanation

  • Line 1: Take the number of test cases( t) as input.

  • Line 3: Start a for loop for each test case.

  • Line 5: Take the number of elements(N) as input.

  • Line 7: Store N space-separated integers in a list (array) as input.

  • Line 10: sumx will store the sum until the current index.

  • Line 11: sumxIndex will store the sumx with respective indices.

  • Example:

    • N = 5

    • Array = [1,3,4,10,5]

      • At index 0 -> sumx=1%5=1 -> sumxIndex = { 1:0 }
      • At index 1 -> sumx=3%5=3 -> sumxIndex = { 1:0 , 3:4 }
      • At index 2 -> sumx=7%5=2 -> sumxIndex = { 1:0 , 3:4 , 2:2 }

  • Line 13: Start for loop from [0-N].

  • Line 14: Since the sum until the ith element = the sum until i-1th element + array[i]. Thus, sumx = ( sumx + array[i] )%N.

  • Line 16: Check if sumx=0.

    • Line 15: If yes, then subarray [0, i] will be the required subarray. Thus, putting left = 0, right = i and breaking the loop.

  • Line 22: Check if sumx already occurred previously in sumxIndex.

    • Line 24: If yes, then left = previous index at which sumx occured in sumxIndex + 1. , right = i and breaks the loop.

  • Line 31: Print the size of found subarray i.e. right-left+1.

  • Line 33: Now, for printing the indices of the subarray starting for loop for i from range = [left,right].

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)