Problem Description

You are given a positive integer num. Your task is to count how many positive integers from 1 to num (inclusive) have an even digit sum.

The digit sum of a number is calculated by adding up all of its individual digits. For example:

• The digit sum of 12 is 1 + 2 = 3
• The digit sum of 234 is 2 + 3 + 4 = 9
• The digit sum of 7 is 7

A number has an even digit sum if the sum of its digits is divisible by 2.

For instance, if num = 12:

• Numbers from 1 to 12 are: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
• Numbers with even digit sums are: 2 (sum=2), 4 (sum=4), 6 (sum=6), 8 (sum=8), 11 (sum=1+1=2)
• The answer would be 5

The solution iterates through all numbers from 1 to num, calculates the digit sum of each number by repeatedly taking the remainder when divided by 10 (to get the last digit) and integer division by 10 (to remove the last digit), then checks if the sum is even by using modulo 2.

Intuition

The most straightforward way to solve this problem is to check each number individually. Since we need to determine if a number has an even digit sum, we must first calculate the digit sum for each number from 1 to num.

To extract digits from a number, we can use the modulo operation. When we divide any number by 10, the remainder gives us the last digit. For example, 234 % 10 = 4. After extracting a digit, we can remove it by performing integer division by 10, which shifts all digits to the right. For instance, 234 // 10 = 23.

By repeatedly applying these two operations - extracting the last digit with % 10 and removing it with // 10 - we can process all digits of a number one by one until the number becomes 0. As we extract each digit, we add it to a running sum.

Once we have the digit sum, checking if it's even is simple: if sum % 2 == 0, the sum is even. We can count how many numbers satisfy this condition by iterating through all numbers from 1 to num and incrementing a counter whenever we find a number with an even digit sum.

This brute force approach works well for this problem because the constraint on num is typically small enough that checking each number individually is efficient. The time complexity is O(num * log(num)) where the log(num) factor comes from the number of digits in each number we need to process.

Learn more about Math patterns.

Solution Approach

The solution uses a simple iterative approach with digit extraction to solve this problem.

Algorithm Steps:

1. Initialize a counter ans = 0 to keep track of numbers with even digit sums.

2. Iterate through each number x from 1 to num (inclusive).

3. For each number x, calculate its digit sum:

   • Initialize a sum variable s = 0
   • While x is not zero:
     • Extract the last digit using x % 10 and add it to s
     • Remove the last digit using integer division x //= 10
   • This loop continues until all digits are processed

4. After calculating the digit sum s, check if it's even:

   • If s % 2 == 0, the digit sum is even
   • Add the boolean result to ans (Python treats True as 1 and False as 0)

5. Return the final count ans

Implementation Details:

The code cleverly uses ans += s % 2 == 0 which adds 1 to ans when the condition is true and adds 0 when false. This is more concise than using an if-statement.

The digit extraction process works because:

• x % 10 gives the rightmost digit (ones place)
• x //= 10 removes the rightmost digit by integer division
• This process repeats until x becomes 0

For example, with number 234:

• First iteration: 234 % 10 = 4, sum becomes 4, x becomes 23
• Second iteration: 23 % 10 = 3, sum becomes 7, x becomes 2
• Third iteration: 2 % 10 = 2, sum becomes 9, x becomes 0
• Loop ends, digit sum is 9

Example Walkthrough

Let's walk through the solution with num = 12.

We need to check each number from 1 to 12 and count those with even digit sums.

Number 1:

• Start with x = 1, s = 0
• Extract digit: 1 % 10 = 1, add to sum: s = 1
• Remove digit: 1 // 10 = 0, loop ends
• Check: 1 % 2 = 1 (odd), don't count it
• ans = 0

Number 2:

• Start with x = 2, s = 0
• Extract digit: 2 % 10 = 2, add to sum: s = 2
• Remove digit: 2 // 10 = 0, loop ends
• Check: 2 % 2 = 0 (even), count it!
• ans = 1

Numbers 3-9: Following the same process:

• 3: digit sum = 3 (odd), ans = 1
• 4: digit sum = 4 (even), ans = 2
• 5: digit sum = 5 (odd), ans = 2
• 6: digit sum = 6 (even), ans = 3
• 7: digit sum = 7 (odd), ans = 3
• 8: digit sum = 8 (even), ans = 4
• 9: digit sum = 9 (odd), ans = 4

Number 10:

• Start with x = 10, s = 0
• First digit: 10 % 10 = 0, s = 0, x = 1
• Second digit: 1 % 10 = 1, s = 1, x = 0
• Check: 1 % 2 = 1 (odd), don't count
• ans = 4

Number 11:

• Start with x = 11, s = 0
• First digit: 11 % 10 = 1, s = 1, x = 1
• Second digit: 1 % 10 = 1, s = 2, x = 0
• Check: 2 % 2 = 0 (even), count it!
• ans = 5

Number 12:

• Start with x = 12, s = 0
• First digit: 12 % 10 = 2, s = 2, x = 1
• Second digit: 1 % 10 = 1, s = 3, x = 0
• Check: 3 % 2 = 1 (odd), don't count
• ans = 5

Final answer: 5 (numbers with even digit sums: 2, 4, 6, 8, 11)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * log₁₀(n)) where n is the input number num.

The outer loop runs from 1 to num, giving us O(n) iterations. For each number x in this range, the inner while loop calculates the sum of digits. The number of digits in a number x is ⌊log₁₀(x)⌋ + 1, which is O(log₁₀(x)). In the worst case, when x = num, this becomes O(log₁₀(n)). Therefore, the overall time complexity is O(n * log₁₀(n)).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. The variables ans, x, and s are the only additional storage used, regardless of the input size. No additional data structures like arrays or recursive call stacks are employed.

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

Common Pitfalls

Pitfall 1: Modifying the Loop Variable Directly

A common mistake is forgetting to use a temporary variable when calculating the digit sum, which would destroy the original loop variable:

Incorrect Code:

def countEven(self, num: int) -> int:
    count = 0
    for x in range(1, num + 1):
        digit_sum = 0
        while x > 0:  # BAD: Modifying loop variable x directly
            digit_sum += x % 10
            x //= 10  # This changes x permanently!
        if digit_sum % 2 == 0:
            count += 1
    return count

This code will fail because after calculating the digit sum of the first number, x becomes 0 and the loop continues with incorrect values.

Solution: Always use a temporary variable to preserve the original value:

temp = x  # Create a copy
while temp > 0:
    digit_sum += temp % 10
    temp //= 10

Pitfall 2: Off-by-One Error in Range

Another mistake is using incorrect range boundaries:

Incorrect Code:

for x in range(num):  # BAD: Missing 1 and num
    # or
for x in range(1, num):  # BAD: Missing num itself

The first case starts from 0 (which isn't a positive integer) and excludes num. The second case excludes num from the count.

Solution: Use range(1, num + 1) to include all numbers from 1 to num inclusive.

Pitfall 3: Integer Division Confusion

In some programming languages or Python 2, division operators behave differently:

Potential Issue:

x = x / 10  # BAD: In Python 3, this gives a float

Using regular division / instead of integer division // will produce floating-point numbers, causing the while loop condition x > 0 to behave incorrectly.

Solution: Always use integer division // when removing digits:

x = x // 10  # Correct: Integer division

Pitfall 4: Inefficient String Conversion Approach

While not incorrect, some might use string conversion which is less efficient:

Less Efficient Code:

digit_sum = sum(int(digit) for digit in str(number))

Although this works and is more readable, it involves string conversion overhead which can be slower for large inputs.

Solution: The arithmetic approach using modulo and integer division is more efficient for this problem, especially when dealing with large ranges.