Problem G
Sharing Candies

Image Credit: Unsplash

Taking care of cats is not easy. You need to constantly keep them happy, and make sure that you treat all your kitties equally.

One day, you come back from work, and realize that your $n$ cats are eagerly waiting for candies. You have $n$ boxes of candies with $c_ i$ candies in the $i^{th}$ box. You want to pick some subset of these boxes to open and use completely. Of course you want to treat all cats impartially, so you want to ensure that the total number of candies you get from these boxes can be divided equally amongst your $n$ cats.

Can you find a non-empty subset of these candy boxes that satisfies the above condition? You do not have to minimize the size of this subset.


The first line of the input a single integer $n$ ($1\leq n \leq 10^6$), denoting both the number of cats and the number of boxes of candies. The second line contains $n$ space separated integers, where the $i^{th}$ integer $c_ i$ ($1\leq c_ i \leq 10^9$) denotes the number of candies in box $i$. Note that the boxes are numbered $1$ to $n$.


If no solution exists, print a single integer $-1$. Otherwise, on the first line of the output, print $m$ ($1\leq m \leq n$), the number of elements in your subset. On the second line of the output, print $m$ space separated integers corresponding to the indices of the box numbers in your chosen subset. The box numbers can be printed in any order. If there are multiple solutions, you can output any.

Sample Input 1 Sample Output 1
3 2 3 1
1 4
Sample Input 2 Sample Output 2
4 2 6 1 2
2 3 5
Sample Input 3 Sample Output 3
1 2 3 10 20 30 100 200 300
1 3 5 9
CPU Time limit 1 second
Memory limit 1024 MB
Nikil Selvam
Source CodeSprint LA 2021
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in