First we have to count the number on 1’s in the string,the to find the possible combinations of no of ones so we use the formula n*(n+1)/2
It could be something like this…
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.
Shouldn’t the answer for Case #2 (i.e.10001) be 4. the sub-strings being 11,101,1001,10001,
instead of 3?
@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
Hi,
I am getting WA. Following is my code. I followed the n(n+1)/2 principle, yet I am not able to clear it.
Kindly point out the mistake.
#include <bits/stdc++.h>
using namespace std;
int main(){
int t, n, count;
string tmp;
cin>>t;
while(t--){
cin>>n;
count = 0;
cin>>tmp;
for(string::iterator i = tmp.begin(); i!=tmp.end();++i){
if(*i=='1'){count++;}
}
cout<<(count*(count+1))/2<<endl;
}
return 0;
}
@insoumniac hope this helps,
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
I am not getting corrct solution.Please check the answer.
#include
#include
using namespace std;
int main() {
// your code goes here
int t,i,j,n,count=0,p,a,k=1;
string b=to_string(k);
``cin>>t;
for(j=1;j<=t;j++)
{
cin>>n;
cin>>a;
string s=to_string(a);
for (i = 0; i < n; i++) {
if (s.substr(i,1) == b) {
count++;
}
}
p=(count*(count+1))/2;
printf("%d\n",p);
}
return 0;
}
Change int to long long
achaitanyasai , thank you for looking into this. I did change it, this is the new solution:CodeChef: Practical coding for everyone
Still WA
nC2 = n*(n-1)/2
@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!
Thanks man
Use char s[n+10]. Always give atleast 1 extra space in case you’re taking input of string as a char array.
Use long instead of int. Overflow is causing WA
Declare p as long long instead of int. Overflow causing WA
Answered the queries as requested.
I have solved this problem now ! I used a different approach ! Thanks !