nC1= combinations taken 1 at a time; or individual 1’s are their own start and end point.
Then nC2 = combinations taken 2 at a time.
Adding these two makes up nC1+nC2=n×(n+1)/2
But I think it should be someting like this…
Example: 111
nC1= 1,1,1
nC2=11,11,11 we can’t include last combination in this sequence because only way to move is forward and last sequence groups last index and first index together.
So nC2 is here actually nC2 - 1 combination = 11,11
Now the last one is
nC3 = 111
So total numbers in the list are 111,11,11,1,1,1
So we have 6 numbers which satisfy this condition.
And n×(n+1)/2 is actually 6.
I am not entirely sure on this…
If you guys have any other explanation please share.
@kalpaj12 what you’re saying is called subsets and not substrings. A substring is a contiguous sequence of characters within a string. so, here the valid substrings would be {1}(1st element of array),{1}(last element of array),{1,0,0,0,1}. Hence, Answer will be 3
first string: 1111
possible ways of getting string of ‘1’ length = 4(length of string)
possible ways of getting string of ‘2’ length = 4-1 = 3(length of string - 1)
possible ways of getting string of ‘3’ length = 4-2 = 2(length of string - 2)
possible ways of getting string of ‘4’ length = 4-3 = 1(length of string - 3)
We sum the ways: 1+2+3+4 = 10(sum of first 4 numbers)
I guess you saw the pattern and how the formula came
@miamiheat- avoid allocating large memory inside the loop … you could have made a static array of max=10^5 outside the loop… here youtry to allocate t*n times inside which is 10^5 * 10^5 … and btw, for this question, you dont have to allocate an array… you could have done input with one variable only!