C++程序，用於刪除數字字串中的字符，使其能被8整除

Given a number in the form of a string, we need to find where to make it divisible by eight after deleting zero or more elements. In other words, we need to find whether there is a subsequence of the string, which is divisible by 8. Return the modified string or -1 if it is not possible.

根據可整除規則，任何最後三位數字可被8整除的數也可被8整除。例如，56992992和476360可被8整除，但2587788不能。如果結果是整數，則原始數可被8整除。

Let us look at some input scenarios that explain the method in detail −

#如果傳遞給該方法的輸入是包含任何可被8整除的子字串的數字字串，則在結果清單中我們可以獲得可被8整除的子字串−

Input: 2567992
Result: 56

如果輸入給方法的是一個不包含任何可被8整除的子字串的數字字串，輸出結果將會回傳為−

Input: 77777777777
Result: -1

Algorithm

• 字串輸入被遍歷，檢查是否有任何子字串是8的倍數。

• If there is any consequent substring present in the input, the substring is returned as the output.

• 如果找到子字串，則程式終止，否則重複步驟2直到找到子字串。

• 如果輸入中沒有可被8整除的子字串，則傳回輸出為-1。

Example

在下面的C 程式中，我們取兩個字串，一個可以轉換成可被8整除的字串，另一個不能，然後找出每種情況下的輸出。我們可以從0到1000迭代，以8的倍數如0、8、16、24、32...1000，並檢查這個數字是否作為給定字串的子序列存在。

#include <iostream>
using namespace std;
int checkIfSubstringExist(string req, string given) {
   int index = 0;
   for (char ch : given) {
      if (req[index] == ch) {
         index++;
      }
   }
   return index == (int)req.size();
}
string solve(string s) {
   for (int i = 0; i < 1e3; i += 8) {
      string num = to_string(i);
      if (checkIfSubstringExist(num, s)) {
         return num;
      }
   }
   return "-1";
}
int main() {

   // the string “95256” can be converted to a string divisible by 8
   // the string “74516” cannot be converted to a string divisible by 8
   // let’s run our code to find the output in each case
   string s1 = "95258", s2="74516";
   cout << solve(s1) << "\n" << solve(s2) << endl;
   return 0;
}

輸出

8
16

As you can see in the above output, 9525 is removed from 95258, and 745 is removed from 74516 to make the left number divisible by 8.

#Conclusion

正如我們所看到的，在簡單觀察之後，我們只需要檢查子集是否存在。我們檢查字串是否包含子序列，最壞情況下，它將檢查整個字串。因此，如果我們給定一個長度為n的數字字串，最壞時間複雜度為O(126*n)，即O(n)。

以上是C++程序，用於刪除數字字串中的字符，使其能被8整除的詳細內容。更多資訊請關注PHP中文網其他相關文章！