To make a number divisible by 4, the minimum number of digits that need to be deleted

In this article, we will explore an interesting computational problem - "the minimum number of digits that need to be removed to make a number divisible by 4". This question is a common question asked in coding competitions and algorithm-based interviews and provides excellent practice for improving your problem-solving skills.

First, let us understand the problem statement: We have a number and our task is to remove the minimum number of digits such that the remaining number is divisible by 4.

Conceptual understanding

The problem lies in the field of number theory. A key fact to understand is that a number is divisible by 4 if and only if its last two digits are divisible by 4. This fact is crucial to solving our problem.

Algorithm description

The algorithm to solve this problem involves the following steps -

• Convert numbers to strings.

• Start from the end of the string and check whether the number composed of the last two characters is divisible by 4.

• If yes, return the number of deleted digits. If not, remove the last character and increment the count.

• Repeat this operation until the number is divisible by 4 or only one digit remains.

Example

This is the C implementation of the algorithm -

#include<bits/stdc++.h>
using namespace std;

int minRemovals(string num) {
   int n = num.size();
   int count = 0;
   
   for (int i = n - 1; i > 0; i--) {
      if ((num[i] - '0' + (num[i - 1] - '0') * 10) % 4 == 0) {
         return count;
      }
      count++;
   }
   
   return n - 1;
}

int main() {
   string num = "1351";
   cout << "Minimum number of digits to be removed to make the number divisible by 4 is: ";
   cout << minRemovals(num) << endl;
   
   return 0;
}

Output

Minimum number of digits to be removed to make the number divisible by 4 is: 3

In the minRemovals function, we initialize the counter count to 0, which will keep track of the number of bits removed. We then iterate from the end of the number (string) and check if the last two digits of the number are divisible by 4. If so, we return the count; otherwise, we return the count. If not, we increment the count and continue with the next iteration.

The main function serves as the entry point to our program where we define the input number and print the minimum number of digits to be removed so that the number is divisible by 4.

Test case example

Let’s take the number 1351 as an example. When we examine the last two digits (51), we see that it is not divisible by 4. Therefore, we remove the last digit (1) and get the number 135. We check again and see that the last two digits (35) are still not divisible by 4. Therefore, we remove the last digit (5), leaving the number 13. The last two digits (13) are not divisible by 4, so we delete the last digit (3). Now, we are left with the number 1, which is not divisible by 4, but we cannot remove any more numbers. Therefore, the minimum number of digits that need to be removed is 3.

Time and space complexity

The time complexity of this algorithm is O(n), where n is the number of digits in the number. The space complexity is O(1) since we are not using any additional data structures in the algorithm.

in conclusion

In this article, we delve into a common computing problem - determining the minimum number of digits that need to be removed to make a number divisible by 4. We develop a concise C solution using key insights from number theory.

The above is the detailed content of To make a number divisible by 4, the minimum number of digits that need to be deleted. For more information, please follow other related articles on the PHP Chinese website!