2180. Count Integers With Even Digit Sum

EasyMathSimulation
Leetcode Link

Problem Description

The task is to find and count all the positive integers up to a given number num whose digits add up to an even sum. For instance, if num is 13, the number 12 would be counted because its digits 1 + 2 equals 3, which is an odd total, and hence its digit sum is not even.

The challenge is to compute the number of these integers efficiently, without having to check each number individually, since that would be too slow for large values of num.

Intuition

The solution takes advantage of patterns in numbers and their sums. The key observations to arrive at the solution approach are:

  1. Every group of ten numbers (0-9, 10-19, etc.) contains exactly five numbers with an even digit sum. This holds because within any such sequence, the sum of the digits changes in a predictable way when moving from one number to the next: the ones place increases by one until it resets at zero when it hits 10, and then the process repeats.

  2. By considering the tens place separately, the solution calculates how many complete tens are in the number num. Multiply that count by 5 (since there are five numbers with an even digit sum in each group of ten) to get a baseline count.

  3. Adjust the baseline count based on the remainder of num when divided by 10 (the last digit of num), and whether the sum of the tens digits is odd or even.

The formula ans = num // 10 * 5 - 1 starts by calculating the baseline even digit sum count, then subtracts 1 to adjust for the starting point (as the sequence starts at 0, not 1).

Next, the code calculates the sum of the tens place digits to determine if the sum, including the ones place of the original num, is even or odd. Depending on this result and the value of the last digit of num, the final answer (ans) must be corrected.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Solution Approach

The provided Python solution uses mathematical reasoning rather than brute force iteration over every number up to num. Here's a detailed breakdown of the implementation:

  • First, it calculates the number of complete tens in num—this tells us how many groups of ten we have to deal with. Each group of ten has exactly five numbers with an even digit sum, hence num // 10 * 5. This gives us a preliminary count.

  • It subtracts 1 from this count by doing ans = num // 10 * 5 - 1 because the sequence we are counting starts from 1 and not 0. For example, if num is 20, without the subtraction, we would count from 0 to 19, but we actually need to count from 1 to 20.

  • Then the algorithm calculates the sum of the tens place digits with the snippet:

    1x, s = num // 10, 0
    2while x:
    3    s += x % 10
    4    x //= 10

    This loops through each digit of num / 10 and adds it to s. The significance of this sum is to determine if the sum of all digits besides the last digit is odd or even, which influences the count adjustment in the subsequent step.

  • Finally, the adjustment is done with the line:

    1ans += (num % 10 + 2 - (s & 1)) >> 1

    Here's what happens in this line:

    • num % 10 gives us the last digit of num.

    • The expression (s & 1) gives us 1 if the sum of tens place digits s is odd, and 0 if it's even.

    • By adding 2 and then subtracting (s & 1), we're effectively deciding whether to add 1 or 2 to the final ans. This accounts for whether the sum will turn even after including the last digit.

    • The >> 1 is a bitwise right shift which divides the number by 2, discarding the remainder. This is used to finally adjust the answer correctly, accounting for the fact that only half of the adjustments (whether we add 1 or 2) result in an even total digit sum.

The key algorithmic patterns used in this solution are mathematical counting and digit manipulation, along with efficient arithmetic operations that replace the need for any complex data structures.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

Example Walkthrough

To illustrate the solution approach, let's consider the number num = 23. We want to find how many positive integers less than or equal to 23 have a digit sum that is even.

Following the steps outlined in the solution approach:

  1. We first calculate the number of complete tens in 23, which is 2 (from 23 // 10). Since each group of 10 has exactly five numbers with an even digit sum, this gives us 2 * 5 = 10 as our preliminary count.

  2. Now, we subtract 1 because we are counting from 1 rather than starting from 0. The count becomes 10 - 1 = 9.

  3. Next, we determine the sum of the tens place digits:

    • 23 // 10 gives us 2.
    • Since 2 is less than 10, the loop terminates after adding 2 to s.
    • The sum of the tens place digits is s = 2, which is even.
  4. The last digit of num (23) is 3 (23 % 10).

  5. Finally, we make the adjustment:

    • s & 1 will evaluate to 0 since 2 (the sum of tens place digits) is even.
    • The correction (num % 10 + 2) >> 1 equals (3 + 2) >> 1, which simplifies to 5 >> 1 or, in other terms, 5 // 2, which equals 2.
  6. Since the tens place sum s is even, there's no need to further adjust the result for this case.

  7. Adding the correction to our count gives 9 + 2 = 11. Therefore, there are 11 numbers less than or equal to 23 with an even digit sum.

To verify our method, we can manually count the numbers with even digit sums up to 23:

  • Even digit sum numbers: 2, 4, 6, 8, 11, 13, 15, 17, 20, 22, 24 (treating 24 as 2 and 4 since we're looking at numbers up to 23)
  • Count of even digit sum numbers: 11

The manual count confirms that our method yields the correct result.

Solution Implementation

1class Solution:
2    def countEven(self, num: int) -> int:
3        # Initial calculation: every group of 10 numbers contains exactly 5 even numbers
4        # If 'num' is 58, then there would be (58 // 10) which is 5 groups of 10, 
5        # each group contributing 5 even numbers, hence 5 * 5 even numbers
6        even_numbers_count = (num // 10) * 5
7
8        # Adjusting the calculation if the sum of digits in 'num' 
9        # makes 'num' itself an even number, this will subtract one from the count.
10        even_numbers_count -= 1
11
12        # Now calculate the sum of the digits for the tens place and greater.
13        # This is to help us determine if the last digit contributes an even or odd number.
14        tens_and_above = num // 10
15        sum_of_digits = 0
16        while tens_and_above:
17            sum_of_digits += tens_and_above % 10
18            tens_and_above //= 10
19
20        # Calculate the adjustment needed for the last digit contribution. 
21        # If the sum of digits (tens place and above) is even, then an
22        # additional even number can be included if the ones place is 1-9, otherwise it's 0-8.
23        # If the sum of digits is odd, then it's off by one either way.
24        # The adjustment uses bitwise operation to quickly determine if 
25        # we need to add one more to the count.
26        last_digit_adjustment = ((num % 10) + 2 - (sum_of_digits & 1)) >> 1
27      
28        # Apply the last digit adjustment to the even numbers count.
29        even_numbers_count += last_digit_adjustment
30      
31        # Return the final count of even numbers.
32        return even_numbers_count
33
1class Solution {
2    // Method to count the number of even digit sum numbers up to a given number
3    public int countEven(int num) {
4        // Initialize a counter for the even sum numbers
5        int evenSumCount = 0;
6      
7        // Loop through all numbers from 1 up to and including 'num'
8        for (int currentNumber = 1; currentNumber <= num; ++currentNumber) {
9            // Variable to store the sum of the digits of the current number
10            int digitSum = 0;
11          
12            // Calculate the sum of the digits of 'currentNumber'
13            for (int x = currentNumber; x > 0; x /= 10) {
14                digitSum += x % 10; // Add the rightmost digit to 'digitSum'
15            }
16          
17            // If the digit sum is even, increment the even sum count
18            if (digitSum % 2 == 0) {
19                ++evenSumCount;
20            }
21        }
22      
23        // Return the total count of numbers with an even digit sum
24        return evenSumCount;
25    }
26}
27
1class Solution {
2public:
3    int countEven(int num) {
4        // Calculate the number of even numbers by integer division by 10 and then multiply by 5.
5        // Subtracted by 1 because the range is from 1 to num-1.
6        int evenCount = (num / 10) * 5 - 1;
7
8        // Calculate the sum of the digits in the quotient when num is divided by 10
9        // This sum is used to determine if the last digit will result in an even total sum.
10        int digitSum = 0;
11        for (int x = num / 10; x > 0; x /= 10) {
12            digitSum += x % 10;
13        }
14
15        // Check if the last digit in num contributes to an even or odd sum.
16        // If digitSum is even, then (num%10 + 2) contributes to having an odd total sum if num's last digit is even.
17        // If digitSum is odd, then (num%10 + 2) contributes to having an even total sum if num's last digit is even.
18        // The right shift by 1 at the end is essentially dividing by 2, which works to calculate the final adjustment.
19        evenCount += ((num % 10) + 2 - (digitSum & 1)) >> 1;
20
21        return evenCount;
22    }
23};
24
1function countEven(num: number): number {
2    // Calculate the number of even tens before the given num
3    let evenCount = Math.floor(num / 10) * 5 - 1;
4  
5    // Initialize the sum of digits variable for tens place
6    let digitSum = 0;
7  
8    // Calculate the sum of digits in the tens place and above
9    for (let x = Math.floor(num / 10); x; x = Math.floor(x / 10)) {
10        digitSum += x % 10;
11    }
12
13    // Check the last digit of num and the parity of digitSum to determine 
14    // if an additional even number should be counted
15    evenCount += ((num % 10) + 2 - (digitSum & 1)) >> 1;
16  
17    // Return the total count of even numbers before and including num
18    return evenCount;
19}
20
Not Sure What to Study? Take the 2-min Quiz:

Which of the following uses divide and conquer strategy?

Time and Space Complexity

The given Python code implements an algorithm that counts how many integers from 1 to num have an even digit sum. The time complexity and space complexity of this algorithm are analyzed as follows:

Time Complexity

  1. The first line within the countEven method, ans = num // 10 * 5 - 1, involves a few constant-time arithmetic operations (integer division, multiplication, and subtraction) and therefore executes in O(1) time.
  2. The while-loop iterates over the number of digits in num // 10, which is proportional to the logarithm of num. Hence, the loop runs in O(log(num)) time.
  3. Inside the loop, again only constant-time operations—modulus, integer division, and accumulation into s—are performed.
  4. The last line outside the loop involves a few more constant-time arithmetic operations, including modulus, addition, bitwise AND, subtraction, and bit-shifting.

Overall, the most time-consuming part of the algorithm is the while-loop, so the time complexity is O(log(num)).

Space Complexity

For space complexity:

  1. The method uses a fixed number of integer variables ans, x, s, and those used for simple calculations. This occupies a constant amount of space.
  2. No additional data structures that grow with the input size are used.
  3. The space taken to store the intermediate results does not depend on the size of num, as it is only affected by the number of digits in num which is logarithmic in size.

Therefore, the space complexity of the algorithm is O(1) as it requires a constant amount of space regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫