Divisible Subset | CodeChef Solution

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

Task

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 <= 10⁵
• Each element of the multiset is a positive integer, not exceeding 10⁹.
• 1 <= N <= 15 : 37 points.
• 1 <= N <= 1000 : 24 points.
• 1 <= N <= 10⁵ : 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 {
	static class FastReader{ 
        BufferedReader br; 
        StringTokenizer st; 
        public FastReader(){br = new BufferedReader(new InputStreamReader(System.in));}
        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 FastReader sc = new FastReader();
	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<>());
	    		hm.get((int)(sum%n)).add(i);
	    	}
	    	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.