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
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}
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 i
th 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+1
th index.
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.
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.
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
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]
sumx
=1%5=1 -> sumxIndex
= { 1:0 }sumx
=3%5=3 -> sumxIndex
= { 1:0 , 3:4 }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 i
th element = the sum until i-1
th element + array
[i
].
Thus, sumx
= ( sumx
+ array
[i
] )%N
.
Line 16: Check if sumx
=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
.
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].
RELATED TAGS
CONTRIBUTOR
View all Courses