拆分二进制数以使每个部分都可被2整除的方式数量

2021年4月24日13:23:22 发表评论 872 次浏览

本文概述

给定一个二进制字符串小号, 任务是找到将其拆分为多个部分的方法, 以使每个部分都能被2.

例子:

输入:S ="100"
输出:2
有两种分割字符串的方法:{"10", "0"}和{"100"}
输入:S ="110"
输出:1

方法:一个观察结果是,字符串只能在0之后拆分。因此,计算字符串中0的数量。我们称这个count为c_0。假设字符串是偶数的情况,除了最右边的0,有两种选择,要么在这个0之后切断字符串,要么不切断字符串。因此,对于偶数字符串,最终的答案是2^(c_zero - 1)。

字符串不能被分割的情况是当它以1结束时。因此,对于奇数字符串,答案将始终为零,因为最后分割部分将始终为奇数。

下面是上述方法的实现:

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

输出如下:

4

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: