数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究检查给定二进制字符串的十进制表示是否可被 K 整除
二进制字符串是由两种不同字符（'0' 和 '1'）组成的字符串，其基数为 2。十进制表示意味着每个数字都在 '0' 到 '9' 之间，其基数为 10。这里我们给出一个二进制数字字符串和一个整数 k，我们需要检查给定二进制字符串的十进制表示是否可被 k 整除。如果可被整除，则返回 'yes'，否则返回 'no'。
在二进制到十进制的转换中，我们使用简单的方法将基数为 2 的数字转换为基数为 10 的数字。例如，如果 1010(2) 是一个二进制数，则其等效的十进制数为 1010(10)。
Input 1: str = “1010” , k = 5 Output 1: yes
说明 - 给定二进制字符串 (1010) 的十进制表示为 10。10 可被 5 整除，因此答案为 'yes'。
Input 2: str = “1100” , k = 5 Output 2: no
说明 - 给定二进制字符串 (1100) 的十进制表示为 12。12 不能被 5 整除，因此答案为 'no'。
我们已经看到了上面给定字符串的示例，让我们来看一下解决方法：
方法一：对于较短的字符串长度
我们可以使用简单的二进制到十进制转换方法来解决这个问题。
让我们逐步讨论这种方法：
首先，我们将创建一个名为 ‘convertBinaryToDecimal’ 的函数，该函数将给定的字符串 ‘str’ 作为参数，并返回字符串 ‘str’ 的十进制表示整数 ‘decimalVal’。
在函数中，我们遍历字符串 ‘str’ 并计算其十进制表示。
在主函数中，创建一个整数 ‘decimalValue’，我们将 ‘convertBinaryToDecimal’ 函数返回的整数存储在其中。
我们创建另一个名为 ‘check’ 的函数，该函数将接收整数 ‘decimalValue’ 和数字 ‘k’，以检查十进制表示是否可被 ‘k’ 整除。
在这个函数中：
如果 ‘decimalValue’ 可被 ‘k’ 整除，则返回字符串 'yes'
否则返回 'no'
注意：此方法仅适用于字符串长度不超过 32 的情况。
示例
#include <bits/stdc++.h>
using namespace std;
long convertBinaryToDecimal( string str ){
long decimalVal = 0;
int len = str.size(); //getting length of the string str
for(int i=0;i<len; i++){
if(str[len-1-i] == '1'){
decimalVal += ( int ) pow( 2 , i );
}
}
return decimalVal;
}
//function to check decimalValue is divisible by k or not?
string check( long decimalValue, int k ){
if( decimalValue % k == 0 ){
return "Yes"; // if it is divisible
} else {
return "No"; // if it is not divisible
}
}
// main function
int main(){
int k = 5; // given number
string str = "1010";// given string
// calling the function 'convertBinaryToDecimal' to convert binary to decimal
long decimalValue = convertBinaryToDecimal( str );
// calling the function 'check' to check whether the 'decimalValue' is divisible by k or not
string result = check( decimalValue, k );
cout<<result;
return 0;
}
输出
Yes
时间和空间复杂度
以上代码的时间复杂度为 O(N*(logN))，因为我们遍历了字符串，并且使用了幂函数会增加 log 因子。
以上代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。
其中 N 是字符串的大小。
方法二：对于较长的字符串长度
如果字符串长度过长，则最佳解决方案如下所示
这里的方法与之前的方法相同，唯一的区别在于我们在将二进制转换为十进制的每一步都对整数 k 取模。
示例
#include <bits/stdc++.h>
using namespace std;
long convertBinaryToDecimal( string str, int k ){
long decimalVal = 0;
int len = str.size(); //getting the length of the string str
// Creating temp variable to store power of two
int temp = 1%k;
if(str[len-1] == '1'){
decimalVal += temp;
decimalVal %= k;
}
// traverse string using for loop for converting binary to decimal
for(int i=1; i<len; i++){
//storing power of two using a previous value of temp
temp = (temp*(2%k))%k;
if(str[len-1-i] == '1'){
decimalVal += temp;
decimalVal %= k;
}
}
//return final reminder left
return decimalVal;
}
//function to check decimalValue is divisible by k or not?
string check( long decimalValue, int k ){
if( decimalValue % k == 0 ){
return "Yes"; // if it is divisible
} else {
return "No"; // if it is not divisible
}
}
// main function
int main(){
int k = 5; // given number
string str = "1010";// given string
// calling the function 'convertBinaryToDecimal' to convert binary to decimal
long decimalValue = convertBinaryToDecimal( str, k );
// calling the function 'check' to check whether the 'decimalValue' is divisible by k or not
string result = check( decimalValue, k );
cout<<result;
return 0;
}
输出
Yes
时间和空间复杂度
以上代码的时间复杂度为 O(N)，因为我们遍历了字符串。
以上代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。
其中 N 是字符串的大小。
结论
在本教程中，我们实现了一个程序来检查给定二进制字符串的十进制表示是否可被 K 整除。我们为短字符串实现了一种方法，为任意字符串大小实现了另一种方法。两种方法的时间复杂度分别为 O(N*(logN)) 和 O(N)。其中 N 是字符串的大小。两种方法的空间复杂度相同，均为 O(1)。
479 次浏览
