# Divisible Subset | CodeChef Solution

Hello coders, today we are going to solve Divisible Subset CodeChef Solution whose Problem Code is DIVSUBS.

You are given a multiset ofÂ NÂ integers. Please find such a nonempty subset of it that the sum of the subset’s elements is divisible byÂ N. Otherwise, state that this subset doesn’t exist.

## Input Format

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 Format

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.

## Constraints

• 1 <= The sum ofÂ NÂ over all the test cases <= 105
• Each element of the multiset is a positive integer, not exceeding 109.
• 1 <=Â NÂ <= 15 : 37 points.
• 1 <=Â NÂ <= 1000 : 24 points.
• 1 <=Â NÂ <= 105Â : 39 points.

Example

Sample Input

``````1
3
4 6 10``````

Sample 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.

## Solution – Divisible Subset

### C++

```#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
int n; cin >> n;
vector<int> v(n + 1); for (int i = 1; i <= n; ++i) cin >> v[i];

for (int i = 1; i <= n; ++i)
v[i] += v[i - 1];

unordered_map<int, int> mp;
mp[0] = 0;

for (int i = 1; i <= n; ++i) {
int x = ((v[i] % n) + n) % n;

if (mp.count(x)) {
cout << i - mp[x] << "\n";

for (int j = mp[x] + 1; j <= i; ++j)
cout << j << " ";

cout << "\n"; return;
} else
mp[x] = i;
}
}

int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int tc; cin >> tc;

while (tc--)
solve();
}

/* Discard subset thinking, such a subarray will always exist since k is <= N, refer images */```

### Python

```# cook your dish here
for t in range(int(input())):
n=int(input())
a=[int(i) for i in input().split()]
store={0:0}
s=0
for i in range(n):
s=(s+a[i])%n
if s in store:
ans=range(store[s]+1,i+2)
break
store[s]=i+1
print(len(ans))
print(*ans)```

### Java

```import java.util.*;
import java.io.*;

class Main2 {
StringTokenizer st;
String next(){while (st == null || !st.hasMoreElements()){try{st = new StringTokenizer(br.readLine());}
catch (IOException  e){e.printStackTrace();}}return st.nextToken();}
int nextInt(){ return Integer.parseInt(next());}long nextLong(){return Long.parseLong(next());}double nextDouble(){return Double.parseDouble(next());}
String nextLine(){String str = ""; try{str = br.readLine(); } catch (IOException e) {e.printStackTrace();} return str; }
}
static long mod = (long)(1e9+7);
//	static long mod = 998244353;
//	static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
public static void main (String[] args) {
int t = 1;
t = sc.nextInt();
z : for(int tc=1;tc<=t;tc++) {
int n = sc.nextInt();
Map<Integer,List<Integer>> hm = new HashMap<>();
long sum = 0;
for(int i=0;i<n;i++) {
int x = sc.nextInt();
sum += (1L*x);
if(!hm.containsKey((int)(sum%n))) hm.put((int)(sum%n), new ArrayList<>());
}
for(int k : hm.keySet()) {
if(k == 0) {
int val = hm.get(k).get(0)+1;
out.write(val+"\n");
for(int i=1;i<=val;i++) out.write(i+" ");
out.write("\n");
continue z;
}else if(hm.get(k).size()>1){
int v1 = hm.get(k).get(0), v2 = hm.get(k).get(1);
out.write((v2-v1)+"\n");
for(int i=v1+1;i<=v2;i++) {
out.write((i+1)+" ");
}
out.write("\n");
continue z;
}
}
}
out.close();
}
private static void sort(int[] a) {List<Integer> k = new ArrayList<>();for(int val : a) k.add(val);Collections.sort(k);for(int i=0;i<a.length;i++) a[i] = k.get(i);}
private static void ini(List<Integer>[] tre2){for(int i=0;i<tre2.length;i++){tre2[i] = new ArrayList<>();}}
private static void sort(long[] a) {List<Long> k = new ArrayList<>();for(long val : a) k.add(val);Collections.sort(k);for(int i=0;i<a.length;i++) a[i] = k.get(i);}
}```

Disclaimer: The above Problem (Divisible Subset) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.