One Strings

Moderate
0/80
Average time to solve is 15m
2 upvotes
Asked in companies
AmazonBarclaysCerner Corporation

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
1
1101
Sample Output 1:
4
Explanation for sample input 1:
In the given test case, there are 3 required substrings of length 1, at indices, 0, 1, and 3. There is also a required substring of length 2 starting at index 0. 
So, there are a total of 4 substrings having only ones.
Sample Input 2:
1
111
Sample Output 2:
6
Explanation for sample input 2:
In the given test case, there are 3 required substrings of length 1, at indices, 0, 1, and 2. There are 2 required substrings of length 2, starting at indices, 0 and 1. There is also a required substring of length 3 starting at index 0. 
So, there are a total of 6 substrings containing only ones.
Hint

Find out all substrings of the given string and check them individually.

Approaches (2)
Brute Force 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:

  1. Define a variable, say strLen, to store the size of the given string.
  2. Initialize a variable, say totalCount=0, to store the total number of substrings containing only ones.
  3. 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.
  4. Finally, we return the value of totalCount.
Time Complexity

O(N ^ 3), where ‘N’ is the length of the given binary string.

 

In order to find out all substrings of the given string, we are looping through all indices and then considering all possible lengths of the substrings starting at that index. This takes O(N^2) time. Now, checking whether a substring contains only ones or not takes another O(N) time. So, the overall complexity becomes O(N^3).

Space Complexity

O(1).

 

We are not using any extra auxiliary space.

Code Solution
(100% EXP penalty)
One Strings
Full screen
Console