Pigeonhole Principle

If more objects are placed into fewer boxes, some box contains at least two objects. Its generalized form says N objects in k nonempty-choice boxes force some box to contain at least ceil(N/k) objects. This is an existence argument, but it often leads directly to an algorithm by tracking the first object in each box. Our application finds a nonempty subarray whose sum is divisible by the array length.

Prerequisites: Prefix sums; normalized modulo; arrays.

Build the idea

1. 1. Identify objects and boxes explicitly

   The principle is useful only after specifying a mapping from every object to one of the boxes. For remainders modulo n there are n boxes, labeled 0..n−1. Placing n+1 prefix sums into them forces two equal residues. The objects are prefixes, not individual array values; using only n element residues would not give the same guarantee.

   $$N>k\Rightarrow \text{some box contains at least two objects}$$

2. 2. Convert equal residues into a subarray

   Let P[j] be the sum of the first j elements, including P[0]=0. If P[i]≡P[j] modulo n with i<j, then P[j]−P[i] is divisible by n. That difference is exactly the nonempty subarray with zero-based indices i..j−1. The prefix difference, not either prefix alone, constructs the witness.

   $$P\left(j\right)\equiv P\left(i\right)\left(\mathrm{mod}n\right)\Rightarrow n\mid \left(P\right(j)-P(i\left)\right)$$

3. 3. Store the first prefix in each box

   Initialize first[0]=0 for the empty prefix and other entries to −1. Scan prefixes j=1..n, normalize the running remainder and inspect its box. If occupied by i, return [i,j−1]; otherwise remember j. A repeated remainder is guaranteed by the final prefix, so the program does not need an arbitrary failure guess.

4. 4. Trace [1,2,4]

   With n=3, empty prefix residue is 0, the next is 1, and after two entries the residue is 0 again. Prefix indices 0 and 2 give interval [0,1] with sum 3, divisible by 3. Signed values are allowed because remainders are normalized; the pigeonhole proof concerns residue classes, not positive sums.

5. 5. Distinguish existence from optimization

   The algorithm returns one guaranteed witness, not the shortest, longest or maximum-sum divisible interval. Those objectives require additional bookkeeping. Other pigeonhole problems involve duplicate birthdays, equal partial states or distances within sorted groups; the main challenge is choosing boxes that turn a collision into the requested property. A claim of “obvious repetition” without a precise count can be false.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Distinguish existence from optimization The algorithm returns one guaranteed witness,
// not the shortest, longest or maximum-sum divisible interval.
#include<iostream>
#include<vector>
int main(){
    int n;
    std::cin>>n;
    std::vector<long long>a(n);
    for(auto&x:a){
        std::cin>>x;
    }
    std::vector<int>first(n,-1);
    first[0]=0;
    long long residue=0;
    for(int j=1;j<=n;++j){
        residue=(residue+a[j-1])%n;
        if(residue<0){
            residue+=n;
        }
        if(first[(int)residue]!=-1){
            int left=first[(int)residue];
            long long sum=0;
            for(int i=left;i<j;++i){
                sum+=a[i];
            }
            std::cout<<left<<' '<<j-1<<'\n'<<sum<<'\n';
            return 0;
        }
        first[(int)residue]=j;
    }
}

Complexity analysis

O(n) time: one residue scan plus at most one witness-sum scan. O(n) storage holds the input and first-prefix table. With 1≤n≤200000 and |aᵢ|≤10^9, any displayed subarray sum fits long long. The mathematical guarantee eliminates a need for exponential search.

Example input and output

Read n in 1..200000 and n signed integers |value|≤10^9. Print zero-based inclusive endpoints of one nonempty subarray with sum divisible by n, then its sum.

Input

3
1 2 4

Output

0 1
3

Prefix sums 0 and 3 share residue zero modulo 3, producing subarray [1,2].

Practical applications

Use for proving duplicates or collisions and finding witnesses among prefix states. It often complements frequency arrays, prefix sums and modular arithmetic. If optimization is required, strengthen the stored information rather than assuming the first collision is optimal.

Check your understanding

Which objects ensure a collision in n residue boxes?

Put it into practice

Find the longest such interval rather than the first one.