You are given a set of N integers. Please find such a non-empty subset of it that the sum of the subset's elements is divisible by N. Otherwise, state that this subset doesn't exist.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test consists of a single integer N - the size of the multiset.
The second line of each test contains N single space separated integers - the multiset's elements.
Output
For each test case output:
-1 if the required subset doesn't exist,
If the required subset exists, output two lines. Output the size of the subset on the first line and output the list of indices of the multiset's element that form the required subset. Of course, any number can be taken in the subset no more than once.
If there are several such subsets, you can output any.
Input:
1
3
4 6 10
Output:
1
2
Explanation
We can pick {6} as the subset, then its sum is 6 and this is divisible by 3 - the size of the initial multiset.
input:
2
4
8 12 18 22
6
1 4 5 9 10 12
output:
1
1
3
2 3 4
input:
1
12
1 2 3 4 5 6 7 8 9 10 11 12
output:
8
1 2 3 4 5 6 7 8
input:
1
5
12 21 32 41 52
output:
3
1 2 3
input:
2
3
21 45 63
5
1 1 2 2 1
output:
1
1
3
2 3 4
hint:
There is always such a subset. Moreover, there is always a consecutive subsegment of any sequence of numbers that corresponds to the multiset’s elements with the sum divisible by the multiset’s size.
Debug the code:
t = int(input())
for case in range(t):
n = int(input())
nos = [int(x) for x in input().split()]
copy = nos[:]
nos[0] = copy[0]%n
if(nos[0] == 0):
print(1)
print(1)
flag = 0
for i in range(1,n):
nos[i] = nos[i-1] + copy[i]
nos[i] = nos[i]%n
if(nos[i] == 0):
print(i+1)
print(*[(x+1) for x in range(i+1)])
flag = 1
if(flag == 1):
continue
flag = 0
index = [x for x in range(n)]
temp = [x for _,x in sort(zip(nos, index))]
for i in range(n-1):
if(nos[temp[i]] == nos[temp[i+1]]):
a = min(temp[i+1],temp[i])
b = max(temp[i+1],temp[i])
print(b-a)
print(*[(x+1) for x in range(a+1,b+1)])
break
Kindly provide the answer using the below link:
https://forms.gle/Sz149hpUp8nNY8EXA