You would have to sort the array B any ways so even if you use count sort you cannot have a complexity better than O(N)
try reading the link given for better clarity at the last of the editorial. basically at any moment if you can form sum (s) using numbers preceding a number (x), but (x > s+1), then you can’t form (sum+1). As, by using the previous numbers, you can only form sum (s), and if you take (x), does not matter which number you add to it (or even if you don’t add any), it will always be greater than (s+1), and hence you will not be able to form (s+1)
What that means is, if we are given numbers in the range [1 to i], then we can form all numbers in the range [1,i*(i+1)/2]. So, for every b[i], we calculate the sum of (1,b[i]-1). Let the maximum number we can create from these numbers is M. The next number we want is M+1, which we can create using b[i]. If b[i+1]> M+1, then it’s impossible to create it and thus ans would be M+1.
1 Like
Will the links to setter’s and tester’s solutions be updated ever?