C++ program to remove characters from a numeric string so that it is divisible by 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.

According to the divisibility rule, any number whose last three digits are divisible by 8 is also divisible by 8. For example, 56992992 and 476360 are divisible by 8, but 2587788 is not. If the result is an integer, the original number is divisible by 8.

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

If the input passed to this method is a numeric string containing any substring divisible by 8, then in the result list we can get the substring divisible by 8−

Input: 2567992
Result: 56

If the input to the method is a numeric string that does not contain any substring divisible by 8, the output result will be returned as −

Input: 77777777777
Result: -1

Algorithm

• The string input is iterated over, checking if any substring is a multiple of 8.

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

• If the substring is found, the program terminates, otherwise step 2 is repeated until the substring is found.

• If there is no substring in the input that is divisible by 8, the returned output is -1.

Example

In the following C program, we take two strings, one that can be converted to a string divisible by 8 and the other that cannot, and find the output in each case. We can iterate from 0 to 1000 in multiples of 8 like 0, 8, 16, 24, 32...1000 and check if this number exists as a subsequence of the given string.

#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;
}

Output

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

As we can see, after simple observation, we only need to check whether the subset exists. We check if the string contains a subsequence, in the worst case it will check the entire string. Therefore, if we are given a numeric string of length n, the worst-case time complexity is O(126*n), which is O(n).

The above is the detailed content of C++ program to remove characters from a numeric string so that it is divisible by 8. For more information, please follow other related articles on the PHP Chinese website!