Number of digits to be removed to make a number divisible by 3 in C++

You are given a number in string. You need to find how many digits need to be removed to make it divisible by 3.

We make a number divisible by removing at most 2 digits. So, the maximum number of digits to be removed to make it divisible by 3 is 2.

Let's see some examples.

Input

92

Output

1

We can remove 2 to make it divisible by 3.

Input

999

Output

0

The given number itself is divisible by 3.

Algorithm

• Initialise the number in string.

• Find the sum of the number.

• If the sum is divisible by 3, then return 0.

• If the sum is not divisible by 3 and the length of the number is 1, then we can't make it divisible by 3. Return -1.

• Iterate over the number.

  • Remove one digit from the number and check the divisibility.

  • If the above condition satisfies, then return 1.

• Check the length of the number again. If the length is 2, then return -1.

• Else return 2.

Implementation

Following is the implementation of the above algorithm in C++

#include <bits/stdc++.h> using namespace std; int getNumSum(string n) {    int len = n.length(), sum = 0;    for (int i = 0; i < len; i++) {       sum += (int)n[i];    }    return sum; } int getDigitsCount(string num) {    int n = num.length();    int sum = getNumSum(num);    if (sum % 3 == 0) {       return 0;    }    if (n == 1) {       return -1;    }    for (int i = 0; i < n; i++) {       int currentDigit = num[i] - '0';       if (sum % 3 == currentDigit % 3) {          return 1;       }    }    if (n == 2) {       return -1;    }    return 2; } int main() {    string num = "7536836";    cout << getDigitsCount(num) << endl;    return 0; }

Output

If you run the above code, then you will get the following result.

1