Number of ways to split a binary number such that every part is divisible by 2

0 0 5 minutes read

Given a binary string S, the task is to find the number of ways to split it into parts such that every part is divisible by 2.

Examples:

Input: S = “100”
Output: 2
There are two ways to split the string:
{“10”, “0”} and {“100”}
Input: S = “110”
Output: 1

Approach: One observation is that the string can only be split after a 0. Thus, count the number of zeros in the string. Let’s call this count c_zero. Assuming the case when the string is even, for every 0 except for the rightmost one, there are two choices i.e. either cut the string after that zero or don’t. Thus, the final answer becomes 2^{(c_zero – 1)} for even strings.
The case, where the string can’t be split is the case when it ends at a 1. Thus, for odd strings answer will always be zero as the last split part will always be odd.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define maxN 20
#define maxM 64
 
// Function to return the required count
int cntSplits(string s)
{
    // If the splitting is not possible
    if (s[s.size() - 1] == '1')
        return 0;
 
    // To store the count of zeroes
    int c_zero = 0;
 
    // Counting the number of zeroes
    for (int i = 0; i < s.size(); i++)
        c_zero += (s[i] == '0');
 
    // Return the final answer
    return (int)pow(2, c_zero - 1);
}
 
// Driver code
int main()
{
    string s = "10010";
 
    cout << cntSplits(s);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG 
{
 
static int maxN = 20;
static int maxM = 64;
 
// Function to return the required count
static int cntSplits(String s)
{
    // If the splitting is not possible
    if (s.charAt(s.length() - 1) == '1')
        return 0;
 
    // To store the count of zeroes
    int c_zero = 0;
 
    // Counting the number of zeroes
    for (int i = 0; i < s.length(); i++)
        c_zero += (s.charAt(i) == '0') ? 1 : 0;
 
    // Return the final answer
    return (int)Math.pow(2, c_zero - 1);
}
 
// Driver code
public static void main(String []args)
{
    String s = "10010";
 
    System.out.println(cntSplits(s));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the approach 
 
# Function to return the required count 
def cntSplits(s) :
 
    # If the splitting is not possible 
    if (s[len(s) - 1] == '1') :
        return 0; 
 
    # To store the count of zeroes 
    c_zero = 0; 
 
    # Counting the number of zeroes 
    for i in range(len(s)) :
        c_zero += (s[i] == '0'); 
 
    # Return the final answer 
    return int(pow(2, c_zero - 1)); 
 
# Driver code 
if __name__ == "__main__" : 
 
    s = "10010"; 
 
    print(cntSplits(s));
     
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
                     
class GFG 
{
 
static int maxN = 20;
static int maxM = 64;
 
// Function to return the required count
static int cntSplits(String s)
{
    // If the splitting is not possible
    if (s[s.Length - 1] == '1')
        return 0;
 
    // To store the count of zeroes
    int c_zero = 0;
 
    // Counting the number of zeroes
    for (int i = 0; i < s.Length; i++)
        c_zero += (s[i] == '0') ? 1 : 0;
 
    // Return the final answer
    return (int)Math.Pow(2, c_zero - 1);
}
 
// Driver code
public static void Main(String []args)
{
    String s = "10010";
 
    Console.WriteLine(cntSplits(s));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

// Function to return the required count
function cntSplits(s) {
  // If the splitting is not possible
  if (s[s.length - 1] == '1') {
    return 0;
  }
 
  // To store the count of zeroes
  let c_zero = 0;
 
  // Counting the number of zeroes
  for (let i = 0; i < s.length; i++) {
    c_zero += (s[i] == '0');
  }
 
  // Return the final answer
  return Math.pow(2, c_zero - 1);
}
 
// Driver code
let s = "10010";
console.log(cntSplits(s));

Output:

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

Efficient approach :

This approach made complexity O(1) by replacing the for loop which counts the number of zeroes with a single statement that calculates the number of zeroes by using the built-in string method ‘replaceAll()’ to remove all the ones and then finding the length of the remaining string, which would be the number of zeroes. Then, instead of using the pow function to calculate 2 raised to the power of c_zero-1, we can use a bit shift operator (c_zero-1) << 1, which will also give the same result but with a constant time complexity of O(1)

C++

#include <iostream>
#include <string>
using namespace std;
 
const int maxN = 20;
const int maxM = 64;
 
// Function to return the required count
int cntSplits(string s) {
    // If the splitting is not possible
    if (s[s.length() - 1] == '1')
        return 0;
 
    // To store the count of zeroes
    int c_zero = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '0') {
            c_zero++;
        }
    }
 
    // Return the final answer
    return (c_zero-1) << 1;
}
 
// Driver code
int main() {
    string s = "10010";
 
    cout << cntSplits(s) << endl;
    return 0;
}
// this code is contributed by dany

Java

// Java implementation of the approach
class GFG
{
    static int maxN = 20;
    static int maxM = 64;
 
    // Function to return the required count
    static int cntSplits(String s)
    {
        // If the splitting is not possible
        if (s.charAt(s.length() - 1) == '1')
            return 0;
 
        // To store the count of zeroes
        int c_zero = s.length() - s.replaceAll("0", "").length();
 
        // Return the final answer
        return (c_zero-1) << 1;
    }
 
    // Driver code
    public static void main(String []args)
    {
        String s = "10010";
 
        System.out.println(cntSplits(s));
    }
}
// this code is contributed by devendra

Python3

class GFG:
    maxN = 20
    maxM = 64
 
    # Function to return the required count
    @staticmethod
    def cntSplits(s):
        # If the splitting is not possible
        if s[-1] == '1':
            return 0
 
        # To store the count of zeroes
        c_zero = len(s) - len(s.replace("0", ""))
 
        # Return the final answer
        return (c_zero-1) << 1
 
# Driver code
if __name__ == '__main__':
  s = "10010"
  print(GFG.cntSplits(s))

C#

// C# implementation of the approach
using System;
 
class GFG {
 
    static int maxN = 20;
    static int maxM = 64;
 
    // Function to return the required count
    static int cntSplits(String s)
    {
        // If the splitting is not possible
        if (s[s.Length - 1] == '1')
            return 0;
 
        // To store the count of zeroes
        int c_zero = 0;
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '0') {
                c_zero++;
            }
        }
 
        // Return the final answer
        return (c_zero - 1) << 1;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        String s = "10010";
 
        Console.WriteLine(cntSplits(s));
    }
}

Javascript

// Javascript program for the above approach
 
class GFG {
  static maxN = 20;
  static maxM = 64;
 
  // Function to return the required count
  static cntSplits(s) {
    // If the splitting is not possible
    if (s[s.length - 1] == "1") {
      return 0;
    }
 
    // To store the count of zeroes
    let c_zero = (s.match(/0/g) || []).length;
 
    // Return the final answer
    return (c_zero - 1) << 1;
  }
}
 
// Driver code
let s = "10010";
console.log(GFG.cntSplits(s)); 
 
 
// contributed by adityasharmadev01

Output

Time complexity : O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!