Count ways to select three indices from Binary String with different adjacent digits
Given a binary string S of length N, the task is to find the number of ways to select three indices such that if they are arranged in increasing order of indices no two adjacent indices will have the same value.
Examples:
Input: S = β00110β
Output: 4
Explanation: Below are the possible valid indices:
=> {0, 2, 4} from β00110β forms β010β
=> {0, 3, 4} from β00110β forms β010β
=> {1, 2, 4} from β00110β forms β010β
=> {1, 3, 4} from β00110β forms β010β
No other selection is valid. Thus, there are 4 total ways.Input: S = β11100β
Output: 0
An approach using the PrefixSum technique.
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 n left and right.
Keep adding the number of ways for every index in the result and finally return it.
Follow the steps below to implement the above idea:
- Initialize a variable totalZero and totalOne to 0, this will keep track of the total number of zeros and ones in the binary string respectively.
- Initialize a variable currZero and currOne to 0, this will keep track of the number of zeros and ones till ith index.
- Iterate over the string
- If the current digit is zero, increment the totalZero by 1
- Otherwise, increment the totalOne by 1
- Initialize a variable result, to keep track of the answer
- Iterate over the string
- If the current digit is 0
- Add the value of (number of ones to the left * number of ones to the right)
- Increment the count of currZero by 1
- Otherwise,
- Add the value of (number of zeros to the left * number of zeros to the right)
- Increment the count of currOnes by 1
- If the current digit is 0
- Finally, return the result.
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 numberOfWays(string s) { int n = s.size(); // Initialize a variable totalZero and // totalOne to 0, this will keep track // of total number of zeros and ones // in the binary string respectively. int totalZero = 0, totalOne = 0; // Initialise variable 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++; } // Initialise a variable 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" ; cout << numberOfWays(s) << endl; // Second test case s = "11100" ; cout << numberOfWays(s) << endl; // Third test case s = "0000" ; cout << numberOfWays(s) << endl; // Fourth test case s = "101" ; cout << numberOfWays(s); return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to find the number of ways static int numberOfWays(String s) { int n = s.length(); // Initialize a variable totalZero and // totalOne to 0, this will keep track // of total number of zeros and ones // in the binary string respectively. int totalZero = 0 , totalOne = 0 ; // Initialise variable 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.charAt(i) == '0' ) { totalZero++; } // Otherwise, increment the // totalOne by 1 else { totalOne++; } } // Initialise a variable result, to // keep track of the answer int result = 0 ; // Iterate over the string 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++; } // 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; } public static void main(String[] args) { // First test case String s = "00110" ; System.out.println(numberOfWays(s)); // Second test case s = "11100" ; System.out.println(numberOfWays(s)); // Third test case s = "0000" ; System.out.println(numberOfWays(s)); // Fourth test case s = "101" ; System.out.println(numberOfWays(s)); } } // This code is contributed by lokeshmvs21. |
Python3
# Python3 code to implement the approach # Function to find the number of ways def numberOfWays(s) : n = len (s); # Initialize a variable totalZero and # totalOne to 0, this will keep track # of total number of zeros and ones # in the binary string respectively. totalZero = 0 ; totalOne = 0 ; # Initialise variable currZero and # currOne to 0, this will keep track # of number of zeros and ones till # ith index. currZero = 0 ; currOne = 0 ; # Iterate over the string for i in range (n) : # If the curr digit is zero # increment the totalZero by 1 if (s[i] = = '0' ) : totalZero + = 1 ; # Otherwise, increment the # totalOne by 1 else : totalOne + = 1 ; # Initialise a variable result, to # keep track of the answer result = 0 ; # Iterate over the string for i in range (n) : # 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 + = 1 ; # 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 + = 1 ; # Finally, return result. return result; # Drivers code if __name__ = = "__main__" : # First test case s = "00110" ; print (numberOfWays(s)); # Second test case s = "11100" ; print (numberOfWays(s)); # Third test case s = "0000" ; print (numberOfWays(s)); # Fourth test case s = "101" ; print (numberOfWays(s)); # This code is contributed by AnkThon |
C#
// C# code to implement the approach using System; public class GFG { // Function to find the number of ways static int numberOfWays( string s) { int n = s.Length; // Initialize a variable totalZero and // totalOne to 0, this will keep track // of total number of zeros and ones // in the binary staing respectively. int totalZero = 0, totalOne = 0; // Initialise variable 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++; } } // Initialise a variable result, to // keep track of the answer int 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; } static public void Main() { // First test case string s = "00110" ; Console.WriteLine(numberOfWays(s)); // Second test case s = "11100" ; Console.WriteLine(numberOfWays(s)); // Third test case s = "0000" ; Console.WriteLine(numberOfWays(s)); // Fourth test case s = "101" ; Console.WriteLine(numberOfWays(s)); } } // This code is contributed by lokesh. |
Javascript
// JavaScript code to implement the approach // Function to find the number of ways const numberOfWays = (s) => { let n = s.length; // Initialize a variable totalZero and // totalOne to 0, this will keep track // of total number of zeros and ones // in the binary string respectively. let totalZero = 0, totalOne = 0; // Initialise variable currZero and // currOne to 0, this will keep track // of number of zeros and ones till // ith index. let currZero = 0, currOne = 0; // Iterate over the string for (let 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++; } // Initialise a variable result, to // keep track of the answer let result = 0; // Iterate over the string for (let 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 // First test case let s = "00110" ; console.log(`${numberOfWays(s)}<br/>`); // Second test case s = "11100" ; console.log(`${numberOfWays(s)}<br/>`); // Third test case s = "0000" ; console.log(`${numberOfWays(s)}<br/>`); // Fourth test case s = "101" ; console.log(`${numberOfWays(s)}<br/>`); // This code is contributed by rakeshsahni |
4 0 0 1
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Articles: