Problem Link
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