Given a string S consisting of only 1’s and 0’s, find the number of substrings which start and end both in 1.
Quick Explanation
You need to find number of pairs of 1.
Explanation
Find total number of 1’s in the given string. Let suppose that the total number of 1’s in the string is n , then the answer is (n*(n+1))/2.
Reason
Let’s suppose that the n 1’s in the string occur at x1 , x2, … , xn position in the string then all substring starting from xi and ending at xj are taken, so total possible ways in taking it is (n*(n+1))/2
Pseudo Code
solve(string s)
int n = 0
for ( i = 0 ; i< s.size() ; i++)
if s[i] == '1'
n++
return (n*(n+1))/2
Due to range (it could cause overflow)…I guess…In highest case value will be (10^5(10^5+1))/2 check the highest value of integer in your compiler by using INT_MAX from . can a int variable hold this much of value?? try long long datatype for holding everything…
Hi,
I did this problem, can anyone please tell what is with my solution as it says wrong answer.I think everything is ok with it. #include #include
using namespace std;
//vector v;
void solve()
{
int n, c = 0;
string s;
cin>>n;
cin>>s;
for(int i = 0; i < n; ++i)
{
if(s[i] == ‘1’)
c++;
}
long long int a = ((c*c) + c)/2;
cout<<a<<endl;
}
int main()
{
int t;
cin>>t;
while(t–)
{
solve();
}
this is the main program of my solution, I don’t think it gives wrong answer also I am using the unsigned long long data type to evaluate the answer, what’s the problem with this solution to the problem?
int main(){
int T;
cin >> T;
for(int i = 0 ; i < T ; ++i){
int N;
cin >> N;
cin.ignore();
string bitString;
getline(cin,bitString);
int countOnes = 0;
for(int j = 0 ; j < (int)bitString.length() ; ++j){
if(bitString[j] == '1')
++countOnes;
}
ULL product = countOnes*(countOnes + 1);
cout << product/2 << endl;
}
return 0;
}
@ankitsablok89 The problem is due to overflow . In your code countOnes in of int type , so when you mutiply countOnes*(countOnes+1) , the ans would be of int type . If countOnes = 10^5 , then overflow would occur . To solve the problem you can cast it to long long type . Here is your corrected
#include<stdio.h>
main()
{
long long int result;
long int i,t,n,count;
char s;
scanf("%ld",&t);
while(t–)
{
count=0;
scanf("%ld",&n);
s = (char)malloc(sizeof(char)(n+1));
fflush(stdin);
gets(s);
for(i=0;i<n;i++)
if(s[i]==‘1’)
count++;
result = (count(count-1))/2 + count;
printf("%lld\n",result);
}
return 0;
}
Someone please clarify : We are essentially choosing two 1’s from a string of n 1’s, so basically, we need to do nC2, right? Then by this the solution should be (n*(n-1))/2! Where am I going wrong?