Count of Groups of Consecutive 1s in a given Binary String

Sample Example

We will take an example so the problem statement will be clear for you. Let's go.

Input:

X = 110101
L = 6

 

Output:

3

 

Explanation:

In the input, there are two variables, X is the binary string, and L is the length of the binary string. Now if we start counting the group of 1's from left, then:

• There are two 1's at the beginning with index [0, 1] = "11".
   
• There is one 1 in the middle with index [3, 3] = "1".
   
• And, one 1 in the last with the index [5, 5] = "1".
   

Hence, the group of 1's in the binary string is 3 (110101).

Now, as the problem statement is clear, let's move to the approach to solve this problem.

Approach 1

We will use a simple stack approach to solve this problem. In data structures, stacks are a linear kind of data structure that refers to the LIFO (Last In, First Out) principle and supports insertion and deletion operations from one end, i.e. the top.

Algorithm

We will now discuss the algorithm for the problem statement stated above.

1. Take two inputs, that is, a string and an integer. The string indicates the binary number (X), and the integer indicates the length of the string (L).
    
2. Call the function countOnesGroup with two parameters, X and L.
    
3. Create an integer type stack, stck.
    
4. Initialize an integer variable count and set it to 0.
    
5. Run a for loop, which will go from 0 to less than L (length of the string). This loop will iterate through each character of the string.
   
   
   1. If the character is equal to 1, push it into the stack.
       
   2. Else check the following conditions:
      
      
      1. If the stack is not empty, increase the count by 1 and pop out all the characters from the stack.
          
      2. Move to step 5.
          
6. If the stack is not empty, increase the count by 1 and return the value of the count.

Dry Run

We have covered the problem statement, example, and algorithm. Now, let's discuss the above algorithm using an input value, i.e., dry run.

Step 1: Let's take the two inputs, where X = 110101 and L = 6.

Step 2: Inside the function countOnesGroup, create an empty stack and an integer variable count. Also, set the count value to 0.

Step 3: Now, we will go inside the for loop. It will check the condition i < L, where L is the length of the binary string. The condition is true because 0 < 6. Hence, it will enter the loop.

• when i = 0:
  It will check here if the first character of X is 1 or not. The answer is Yes. So, 1 will be pushed into the stack.

Now, again it will check the condition i < L, which is true as 1 < 6. So, it will enter the loop for the second time.

• when i = 1:
  It will again check if the next character of X is 1. The answer is Yes. So, 1 will be pushed into the stack.

Now, again it will check the condition i < L, which is true again as 2 < 6. So, it will enter the loop for the third time.

• when i = 2:
  It will check if the next character of X is 1. The answer is No. The next character is 0 here, so we will move to the else part.
  
  
  • Here, it will check if the stack is empty or not. The answer is "Not empty". So, it will increase the count by 1 and pop the characters present inside the stack until it becomes empty.

Now, again it will check the condition i < L, which is true as 3 < 6. So, it will enter the loop for the fourth time.

• when i = 3:
  It will check if the next character of X is 1. The answer is Yes. So, 1 will be pushed into the stack again.

Again it will check the condition i < L, which is true again as 4 < 6. So, it will enter the loop for the fifth time.

• when i = 4:
  It will check if the next character of X is 1. The answer is No. The next character is 0 here, so we will move to the else part.
  
  
  • We will follow the same step as when i = 2. It will check here if the stack is empty or not. The answer is "Not empty". So, it will increase the count by 1 and pop the characters present inside the stack until it becomes empty.

Now, it will check the condition i < L, which is true again as 5 < 6. So, it will enter the loop for the fifth time.

• when i = 5:
  It will check if the next character of X is 1. The answer is Yes. So, 1 will be pushed into the stack again.

Again it will check the condition i < L, which is false this time as 6 < 6 is not true. So it will come out of the loop this time.

Step 4: If the stack is not empty, increase the count by 1. So, as you can see in the above step, the stack is not empty. Hence the count will increase from 2 to 3.

Step 5: Return the value of the count and print the output as 3.

As the dry run is clear for you with a proper example, let's move to the implementation in three languages, i.e., Java, C++, and Python.

Implementation in Java

import java.util.*;
 
class Solution{

    static int countOnesGroup(String X, int L) {
    
        Stack<Integer> stck = new Stack<>();
        int count = 0;
    
        for(int i = 0; i < L; i++) {
            if (X.charAt(i) == '1')
                stck.push(1);
                
            else {
                if (!stck.empty()) {
                    count++;
                    while (!stck.empty()) {
                        stck.pop();
                    }
                }
            }
        }

        if (!stck.empty())
            count++;
    
        return count;
    }
    
    public static void main(String[] args) {
        
        String X = "110101";
        int L = 6;
    
        System.out.println("Count of 1's group is "+countOnesGroup(X, L));
    }
}

 

Output:

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int countOnesGroup(string X, int L) {
    stack<int> stck;
    int count = 0;

    for (int i = 0; i < L; i++) {
        if (X[i] ==  '1')
            stck.push(1);

        else {
            if (stck.empty() == false) {
                count++;  
                while (stck.empty() == false) {
                    stck.pop();
                }
            }
        }
    }

    if (!stck.empty())
        count++;

    return count;
}

int main() {
    string X = "110101";
    int L = 6;

    cout << "Count of 1's group is " <<countOnesGroup(X, L);
    return 0;
}

 

Output:

Implementation in Python

def countOnesGroup(X, L):
    stck = []
    count = 0

    for i in range(L):
        if (X[i] == '1'):
            stck.append(1)
            
        else:
            if (len(stck) > 0):
                count += 1
                while (len(stck) > 0):
                    stck.pop()
                    
    if (len(stck)):
        count += 1

    return count
    
if __name__ == '__main__':
    
    X = "110101"
    L = 6
    
    print("Count of 1's group is",countOnesGroup(X, L))

 

Output:

Time Complexity

The time complexity of the given algorithm is O(N). Here, N is the length of the binary string. The reason is we are iterating the binary string from the beginning to the end. Hence, it will take O(N) time to complete the iteration.

Space Complexity

The space complexity of the given algorithm is O(N), as we are using a stack to hold 1’s in the string and which can go up to N. Hence, the space complexity is O(N).

Approach 2

In the last approach, we used a stack to hold the indexed character. In this approach, we will perform the same tasks without stack. This will help us to reduce the space complexity. 

Let's look at the algorithm first.

Algorithm

The algorithm for this approach will be as follows:

• Take two variables, X and L, where X is the binary string, and L is the length of the string.
   
•  Initialize two integer variables, count and ans, and set them to 0.
   
• Run a for loop, which will go from 0 to less than L (length of the binary string). This loop will iterate through each character of the string.
  
  
  • If the current character is equal to 1, increase the count.
     
  • Else, check if the count is greater than 0. If yes, increase the ans variable by 1 and set the count to 0.
     
• If the value of count is not zero, increase ans by 1 and print the ans.

Dry Run

As we are clear with the algorithm, let's check the dry run with the input values.

Step 1: Let's take two variables, where X = "110101" and L = 6.

Step 2: Set count = 0 and ans = 0.

Step 3: Now, we will go inside the for loop. It will check the condition i < L, where L is the length of the binary string. The condition is true because 0 < 6. Hence, it will enter the loop.

• when i = 0: 
  count = 0; ans = 0; i = 0; X = 110101;
  It will check if the first character of the X is 1. The answer is Yes. So, it will increase the count by 1.
  
  Check if i < L, the condition is true. Hence we will enter the loop again.
   
• when i = 1:
  count = 1; ans = 0; i = 1; X = 110101;
  Again, it will check if the next character of the X is 1. The answer is Yes. So, it will increase the count by 1.
  
  Check if i < L, the condition is true. Hence we will enter the loop again.
   
• when i = 2:
  count = 2; ans = 0; i = 2; X = 110101;
  Again, it will check if the next character of the X is 1. The answer is No. So, it will move to the else part. 
  
  Inside else, it will check if the count is greater than 0. The answer is Yes, as the count is 2 in this step. So, it will increase the ans variable by 1 and set the count to 0.
  
  Check if i < L, the condition is true. Hence we will enter the loop again.
   
• when i = 3:
  count = 0; ans = 1; i = 3; X = 110101;
  Again, it will check if the next character of the X is 1. The answer is Yes. So, it will increase the count by 1.
  
  Check if i < L, the condition is true. Hence we will enter the loop again.
   
• when i = 4:
  count = 1; ans = 1; i = 4; X = 110101;
  Now, it will check if the next character of the X is 1. The answer is No. So, it will move to the else part. 
  
  Inside else, it will check if the count is greater than 0. The answer is Yes because the count is 1 in this step. So, it will increase the ans variable by 1 and set the count to 0.
  
  Check if i < L, the condition is true. Hence we will enter the loop again.
   
• when i = 5:
  count = 0; ans = 2; i = 5; X = 110101;
  Here, it will again check if the current character is 1. Yes, the current character is 1. So it will increase the count by 1.
  
  Check if i < L, the condition is false as i is now 6 and 6 < 6 is not true. Hence we will not enter the loop again.
  
  The final values of the count and ans at the end are as follows:
  count = 1; ans = 2;

 

Step 4: If the value of count is not zero, increase ans by 1. So the ans will be 3.

Step 5: Print the ans.

Implementation in Java

public class Solution {
    public static void main(String[] args) {
        String X = "110101";
        int L= 6;
    
        int count = 0, ans = 0;
        for(int i=0;i<L;i++){
            if(X.charAt(i)=='1'){
                count++;
            }else{
                if(count>0){
                    ans++;
                    count = 0;
                }
            }
        }
        if (count!=0)
            ans=ans+1;  
        System.out.println("Count of 1's group is "+ans);
        }
}

 

Output:

Implementation in C++

#include <iostream>
using namespace std;

int main() {
    string X = "110101";
    int L= 6;
    
    int count = 0, ans = 0;
    for(int i=0;i<L;i++){
        if(X[i]=='1'){
            count++;
        }else{
            if(count>0){
                ans++;
                count = 0;
            }
        }
    }
    ans+=(count!=0);
    cout<<"Count of 1's group is "<<ans<<endl;
    return 0;
}

 

Output:

Time Complexity

The time complexity of the given algorithm is O(N). Here, N is the length of the binary string. The reason is we are iterating the binary string from the beginning to the end. Hence, it will take O(N) time to complete the iteration.

Space Complexity

The space complexity of this approach is less than the previous approach, which is O(1). The reason is we took only constant space in the form of a few variables.

Must read decimal to binary c++ 

Frequently Asked Questions

What is a Binary String?

A string of bytes is known as a binary string. It generally consists of 0's and 1's in them.

Define Stack.

Stacks are a linear kind of data structure that refers to the LIFO (Last In, First Out) principle.

What is the time complexity for converting a decimal number to binary?

The time complexity for converting a decimal number to binary is O(logN), where N is the number.

What is time complexity?

The amount of time an algorithm or code takes to execute each instruction is known as its time complexity.

What is space complexity?

The total memory space used by an algorithm or code, including the space of input values, is referred to as "space complexity".

Conclusion

This article discusses the topic of the count of groups of consecutive 1s in a given Binary String. In detail, we have seen the problem statement, sample example, algorithm, dry run, and implementation in three languages. Along with this, we also saw the time and space complexity.

We hope this blog has helped you enhance your knowledge of the count of groups of consecutive 1s in a given Binary String. If you want to learn more, then check out our articles.

• Check if a string is a palindrome
• String Hashing
• Car fleet
   

And many more on our platform Coding Ninjas Studio.

Recommended problems -

• Beautiful String
• Subsequence of a String
• Find the Shortest Substring in a String

 

Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Happy Learning!