Last Updated: 21 Apr, 2021

One Strings

Moderate

Asked in companies

Solve now

Problem statement

You are given a binary string ‘STR’, containing only zeroes and ones.

Your task is to determine the total number of substrings having only ones.

Input Format:

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains a single string, 'STR',

Output Format:

For each test case, print a single line containing a single integer, denoting the total number of substrings containing only ones.

The output for each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= |STR| <= 10 ^ 5

Where ‘T’ denotes the number of test cases and |STR| represents the total length of the string, ‘STR’.

Time Limit: 1 sec.

Solve now

Approaches

01 Approach

Approach:

The approach is to find all substrings of the given string and then check each substring individually whether it contains all ones or not. We can check this by traversing through the entire string and if any character is zero, then this substring does not contain only ones. But if there is no zero in this substring then this substring contains only ones and thus we can increase the value of our answer by 1.

Steps:

Define a variable, say strLen, to store the size of the given string.
Initialize a variable, say totalCount=0, to store the total number of substrings containing only ones.
Run a loop from idx=0 to idx<strLen, and do:
1. Run another loop from substrLen=1 to substrLen<=strLen-idx, and do:
  1. Now, we need to check whether the string starting at index idx, having a length of substrLen, contains only ones or not.
  2. Declare a boolean variable, say isOneString = true. This will tell us whether the substring contains only ones or not.
  3. Run another loop from I = idx to I < idx+substrLen, and do:
    1. If str[i]==’0’, then this means that the substring does not contain only ones. Hence, we make isOneString = false and break out of the loop.
  4. If isOneString is still true, that means that this substring contains only ones and we increase the value of our final answer, totalCount by one.
Finally, we return the value of totalCount.

Solve now

02 Approach

Approach:

The approach is to observe the fact that if a string of length ‘N’ contains only ones, then this string also contains within itself, ‘N’ substrings of length 1, ‘N-1’ substrings of length 2, and so on and so forth till 1 substring of length ‘N’, which was also the original string. Let’s call this bigger string of length ‘N’, a block. So, a block of length ‘N’ contains (N*(N+1))/2 substrings containing only ones and we can add this value to our answer. Thus, we can calculate our final result by adding this value for every block.

Steps:

Define a variable, say strLen, to store the size of the given string.
Initialize a variable, say totalCount=0, to store the total number of substrings containing only ones.
Initialize a variable, say blockLen=0, to store the length of all blocks of strings one by one as we move through them.
Run a loop from idx=0 to idx<=strLen, and do:
1. If str[idx] == ‘1’, increase the value of blockLen by 1.
2. Else if, str[idx] == ‘0’ or idx==strLen, this means that the current block has ended so we need to do:
  1. Add the value of (blockLen*(blockLen+1) / 2 to the value of totalCount.
  2. Make the value of blockLen = 0. This is because we need to calculate the value of the next block.
Return the value of totalCount.

Solve now