資料結構
網路
關係資料庫管理系統 (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 次瀏覽
