15,968,278 members
5.00/5 (1 vote)
See more:
Given and string we need to find out the total number of substrings in which 1's are greater than 0's.

I approached this problem using Dynamic programming but I was not able to come up with a solution, I am successful in writing a naive-logic but I was not able to optimize the code (i.e time limit is exceeding)

Any help in optimizing or suggestions for a new approach will be help full. The time complexity of below code is O(n^3) Any solutions to reduce the time-complexity will be helpfull.

Note: The input is only series of 1's and 0's

Note:A substring is a contiguous sequence of characters within a string. For more information about substrings visit Wikipedia

What I have tried:

C++
```#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main(){
int tc =0; //total count
string st; //original string
getline(cin,st);
int lent = st.size(); //size of string
for(int i =0;i<lent;i++){ //loop to generate all possible substrings
int j = lent-1;
while(j>=i){

string st1(st.begin()+i,st.end()-j+i); // A substring
int c1 = count(st1.begin(),st1.end(),'1'); // count of 1's in substring
if(c1 > st1.size()-c1) tc++; // Condition to check if 1's are more
j--;
}
}
cout << tc; // Print total substrings
}```
Posted
Updated 12-Jul-21 2:51am

## Solution 1

While we are more than willing to help those that are stuck, that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you. And "code challenges" count as homework!

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]

pendela neelesh 12-Jul-21 4:46am
I am preparing for interviews and I was stuck with this problem , I tried the code mentioned in the question but it was rejected saying time limit exceeded, I tried by taking all the substrings and count number of ones in that substring then compared it with number of zeroes, if ones are more I incremented the TotalCount(tc) by 1.
OriginalGriff 12-Jul-21 4:55am
The whole idea of the challenge - particularly in the light of an interview - is to find out how you think, how you react to situations and tasks: not how I react!

So you tried an approach, and it didn't work, because it was a "brute force" approach, and it wasn't in any way "clever" or "refined".
Think about the task, and how you might be able to approach it in a non-brute force approach! Think about what you know about the string and the task requirements.

## Solution 3

Quote:
I was not able to optimize the code (i.e time limit is exceeding)

With challenge sites, simple minded code is never the solution, you need to be agile in your head. And you need to avoid language features that make your life easier because they cost.

In the inner loop, you create a new string just to count the number of '1', this string is the difference between O(n)=N^3 and O(n)=N^2.
In the inner loop, what is the difference between 2 consecutive strings ? a single char !
Knowing number of '1' and '0' in previous string, do you need to recount everything or just update the number of '1' and '0' for this single char ?

CPallini 12-Jul-21 9:18am
5.
Patrice T 12-Jul-21 9:23am
Thank you.