Categories
28°C, New York
Home Data Structures and Algorithms Bitwise OR Triplets in a Binary String

Bitwise OR Triplets in a Binary String

Bitwise AND of N binary strings

Given a binary string S of length N, where S[i] represents an integer value. the task is to count the number of ways to choose three different indices ( 0 <= i < j < k < N) such that the bitwise OR of the adjacent chosen element should be one (i.e, S[i] OR S[j] == 1 AND S[j] OR S[k] == 1).

Examples:

Input: S = “00110”
Output: 4
Explanation: Below are the different possible three indices:

  • indices {0, 2, 4} forms “010” such that S[0] | S[2] == 1 && S[2] | S[4] == 1
  • {0, 3, 4} forms “010”such that S[0] | S[3] == 1 && S[3] | S[4] == 1
  • {1, 2, 4} forms “010” such that S[1] | S[2] == 1 && S[2] | S[4] == 1
  • {1, 3, 4} forms “010” such that S[1] | S[3] == 1 && S[3] | S[4] == 1

Thus, there are 4 total ways.

Input: S = “11100”
Output: 0

Bitwise OR Triplets in a Binary String using PrefixSum Technique:

The idea is of Keep track of the number of zeros and ones on the left and right at any indices. At any index i, if the ith digit is zero then for this index we can select (number of ones on the left * number of ones on the right). Similarly, if the digit is 1, check for the 0s to the left and right. Keep adding the number of ways for every index in the result and finally return it.

Step-by-step approach:

  • Calculate the totalZero and totalOne in the binary string.
  • Initialize currZero and currOne to 0 to keep track of the number of zeros and ones until the current index i.
  • Initialize a variable result to keep track of the answer.
  • Iterate through the string:
    • If the current digit is ‘0’:
      • Add the value of (number of ones to the left * number of ones to the right) to result.
      • Increment currZero by 1.
    • If the current digit is ‘1’:
      • Add the value of (number of zeros to the left * number of zeros to the right) to result.
      • Increment currOne by 1.
  • Finally, return result as the answer.

Below is the implementation of the above approach:

C++




// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of ways
long long countWays(string s)
{
    int n = s.size();
 
    // Initialize a varaible totalZero and
    // totalOne to 0, this will keep track
    // of total number of zeros and ones
    // in the binary staring respectively.
    int totalZero = 0, totalOne = 0;
 
    // Initilise varaible currZero and
    // currOne to 0, this will keep track
    // of number of zeros and ones till
    //  ith index.
    int currZero = 0, currOne = 0;
 
    // Iterate over the string
    for (int i = 0; i < n; i++) {
 
        // If the curr digit is zero
        // increment the totalZero by 1
        if (s[i] == '0')
            totalZero++;
 
        // Otherwise, increment the
        // totalOne by 1
        else
            totalOne++;
    }
 
    // Initilise a varible result, to
    // keep track of the answer
    long long result = 0;
 
    // Iterate over the string
    for (int i = 0; i < n; i++) {
 
        // If the current digit is 0
        if (s[i] == '0') {
 
            // Add the value of (number of
            // ones to the left * number
            // of ones to the right)
            result += (currOne * (totalOne - currOne));
 
            // Increment the count of
            // currZero by 1
            currZero++;
        }
 
        // Otherwise, Add the value of
        // (number of zeros to the left
        // * number of zeros to the right)
        else {
            result += (currZero * (totalZero - currZero));
 
            // Increment the count of
            // currOnes by 1
            currOne++;
        }
    }
 
    // Finally, return result.
    return result;
}
 
// Drivers code
int main()
{
    // First test case
    string s = "00110";
 
    // Function Call
    cout << countWays(s) << endl;
 
    return 0;
}
 






                        









Java














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















import java.util.*;


 


public class Main {


    // Function to find the number of ways


    static long countWays(String s) {


        int n = s.length();


 


        // Initialize variables totalZero and totalOne to 0


        int totalZero = 0, totalOne = 0;


 


        // Initialize variables currZero and currOne to 0


        int currZero = 0, currOne = 0;


 


        // Iterate over the string


        for (int i = 0; i < n; i++) {


            // If the current digit is '0', increment totalZero


            if (s.charAt(i) == '0')


                totalZero++;


            // Otherwise, increment totalOne


            else


                totalOne++;


        }


 


        // Initialize the result variable to keep track of the answer


        long result = 0;


 


        // Iterate over the string again


        for (int i = 0; i < n; i++) {


            // If the current digit is '0'


            if (s.charAt(i) == '0') {


                // Add the value of (number of ones to the left * number of ones to the right)


                result += (currOne * (totalOne - currOne));


 


                // Increment the count of currZero by 1


                currZero++;


            } else {


                // Add the value of (number of zeros to the left * number of zeros to the right)


                result += (currZero * (totalZero - currZero));


 


                // Increment the count of currOne by 1


                currOne++;


            }


        }


 


        // Finally, return the result


        return result;


    }


 


    public static void main(String[] args) {


        // Test case


        String s = "00110";


 


        // Function Call


        System.out.println(countWays(s));


    }


}



















                        







                        









Python3














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















# Python Implementation


def countWays(s):


    n = len(s)


    totalZero = 0


    totalOne = 0


    currZero = 0


    currOne = 0


 


    for i in range(n):


        if s[i] == '0':


            totalZero += 1


        else:


            totalOne += 1


 


    result = 0


 


    for i in range(n):


        if s[i] == '0':


            result += (currOne * (totalOne - currOne))


            currZero += 1


        else:


            result += (currZero * (totalZero - currZero))


            currOne += 1


 


    return result


 


# Test case


s = "00110"


print(countWays(s))


 


# This code is contributed by Tapesh(tapeshdua420)



















                        







                        









C#














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















using System;


 


class Program


{


    // Function to find the number of ways


    static long CountWays(string s)


    {


        int n = s.Length;


 


        // Initialize variables to track total number of zeros and ones


        int totalZero = 0, totalOne = 0;


 


        // Initialize variables to track number of zeros and ones till ith index


        int currZero = 0, currOne = 0;


 


        // Iterate over the string


        foreach (char c in s)


        {


            if (c == '0')


                totalZero++;


            else


                totalOne++;


        }


 


        // Initialize a variable 'result' to keep track of the answer


        long result = 0;


 


        // Iterate over the string


        for (int i = 0; i < n; i++)


        {


            // If the current digit is 0


            if (s[i] == '0')


            {


                // Add the value of (number of ones to the left * number of ones to the right)


                result += (currOne * (totalOne - currOne));


                currZero++;


            }


            else


            {


                // Add the value of (number of zeros to the left * number of zeros to the right)


                result += (currZero * (totalZero - currZero));


                currOne++;


            }


        }


 


        // Finally, return result


        return result;


    }


 


    // Driver code


    static void Main()


    {


        // First test case


        string s = "00110";


 


        // Function call


        Console.WriteLine(CountWays(s));


    }


}



















                        







                        









Javascript














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















// JavaScript code to implement the approach


 


// Function to find the number of ways


function countWays(s) {


    const n = s.length;


 


    // Initialize variables totalZero and totalOne to 0


    let totalZero = 0,


        totalOne = 0;


 


    // Initialize variables currZero and currOne to 0


    let currZero = 0,


        currOne = 0;


 


    // Iterate over the string


    for (let i = 0; i < n; i++) {


        // Increment totalZero or totalOne based on the digit


        if (s[i] === '0')


            totalZero++;


        else


            totalOne++;


    }


 


    // Initialize a variable result to keep track of the answer


    let result = 0;


 


    // Iterate over the string again


    for (let i = 0; i < n; i++) {


        if (s[i] === '0') {


            // Add the value of (number of ones to the 


            // left * number of ones to the right)


            result += (currOne * (totalOne - currOne));


            currZero++;


        } else {


            // Add the value of (number of zeros to the 


            // left * number of zeros to the right)


            result += (currZero * (totalZero - currZero));


            currOne++;


        }


    }


 


    // Finally, return result


    return result;


}


 


// First test case


const s = "00110";


 


// Function Call


console.log(countWays(s));



















                        







                        









													
													
												

												
												

													
													
Output


4










													
													
												

												
												

													
													
Time Complexity: O(N)
Auxiliary Space: O(1)

													
													
												

												
												

													
													

													
													
												

												
												

													
													

													
													
												

												
												

													
													

													
													
												

												
													
											

											
										

									

									

										
										
Tags:

										
										#Geeks Premier League 2023
										
										#prefix-sum
										
										#DSA
										
										#Geeks Premier League
										
										#Strings
										
										#prefix-sum
										
										#Strings
										
										

									

									

										

											
										

										

											
											
												Bitwise AND of N binary strings