Subarray Sum - Editorial

Problem Link

Practice

Contest

Author Rishab Pati

Tester Rajat De

Editorialist Rajat De

Difficulty

Medium

Pre-requisites - Maths , Modulo , Pigeonhole Principle

Problem: Find all numbers which will definitely appear in subarray-set of all arrays of length ‘N’ with sum ‘S’.

Quick Explaination : This problem can be solved easily if we can see for all i from 1 to S if there is any array where i does not occur in its subarray set.

Explaination:

If a number ‘X’ occurs in subarray set of ‘A’ , then it means that there are indices [i , j] such that 0 <= i <= j <= n and sum of elements from i to j is ‘X’.

If we construct the prefix sums of this array (an array P such that P[i] = P[i - 1] + array[i]) , then ‘X’ is in its array’s subarray set if we have [i , j] such that P[i] - P[j] = ‘X’.

Now we want to see if there is any array where there are no 2 indices i , j such that P[i] - P[j] = ‘X’.

Now to do this , we group numbers according to their modulo ‘X’.

Suppose we have S = 9 , and we want to avoid getting the element say ‘3’ in its subarray set.

Then we must not have P[i] - P[j] = 3 in any case

so lets group all numbers from 0 to 9 according to their modulo 3

The groups are

1 4 7

2 5 8

0 3 6 9

Now we want to construct the prefix sum array.

If we take 2 consecutive numbers from the same group , then we will have 2 elements in P whose difference is 3 so 3 will occur in its subarray set.

So for the first 2 groups we take ceil(group size / 2) elements.

In the last group , its compulsory to take 0 since P[0] = 0 , now we cant choose the second value in this set, among the rest of the elements , we can again choose (ceil(remaining elements) / 2) elements which is 0 here.

So total we can have 2 + 2 + 2 = 6 elements . so if n <= 6 then we can avoid getting 3 in subarray set but if n is > 6 , then we must choose one more number from this group but then we will have 2 or more consecutive numbers from the same group (using pigeonhole principal)

Now to implement this for a general N, S, X , we loop X from 1 to S , now we need to write an efficient function for checking if X occurs in its subarray set or not.

We have S % X normal groups of size (S / X) + 1 , and (X - (s % X) - 1) groups of size (S / X) and 1 special group of size (s / x) + 1 (note that the division here is integral division)

From a normal group you can take ceil(size / 2) elements and from the special group you can take 1 + ceil((group size - 2) / 2) elements.

Just check if this value is >= N or not.

here is the code

bool check(int x){
    if(x == s){
        return 1; // S always appears in subarray set since P[n] = S and P[0] = 0 , so P[n] - P[0] = S
    }
    int sz1 = (s / x) + 1;
    int cnt1 = s % x;//number of normal groups of size (s / x) + 1
    int sz2 = s / x;
    int cnt2 = x - cnt1 - 1;//number of normal groups of size (s / x)
    int cnt = ((sz1 >> 1) + (sz1 & 1)) * cnt1;//this is equivalent to writing ceil(normal group size / 2) * count
    cnt += ((sz2 >> 1) + (sz2 & 1)) * cnt2;
    sz1 -= 2;//special group , we must choose the number 0 and must not choose the next number
    cnt += ((sz1 >> 1) + (sz1 & 1));
    return cnt < n;
}

Author’s Solution

Tester’s Solution

2 Likes

Don’t we also have to consider that P[N] = S as the sum of the array elements is S?
Also, isn’t 1 + ceil((group size - 2) / 2) = 1 + ceil(((group size/ 2) - 1) = ceil((group size/2))) ?