Solution Explanation

The problem asks to count the number of positive integers less than or equal to a given number num whose digit sums are even. The solutions presented use two different approaches:

Solution 1 (Brute Force):

This approach iterates through each number from 1 to num. For each number, it calculates the sum of its digits and checks if the sum is even. If it is, the counter ans is incremented.

• Time Complexity: O(N*logN), where N is num. The outer loop iterates N times, and the inner loop (digit sum calculation) takes at most log10(N) time (since the number of digits is proportional to the logarithm of the number).

• Space Complexity: O(1). The solution uses a constant amount of extra space.

Solution 2 (Optimized):

This approach is more efficient. It leverages the observation that roughly half the numbers will have an even digit sum. It first calculates the number of integers with an even digit sum in multiples of 10 (num // 10 * 5 - 1). Then it handles the remaining numbers (those between num // 10 * 10 and num) by individually checking their digit sums.

• Time Complexity: O(logN). The loop iterates at most log10(N) times (to calculate the digit sum of num // 10).

• Space Complexity: O(1). The solution uses a constant amount of extra space.

Code Explanation (Python)

Solution 1 (Python):

class Solution:
    def countEven(self, num: int) -> int:
        ans = 0
        for x in range(1, num + 1):
            s = 0
            while x:
                s += x % 10
                x //= 10
            ans += s % 2 == 0
        return ans
 

This code iterates from 1 to num. Inside the loop:

1. s = 0: Initializes a variable s to store the sum of digits.
2. while x:: This loop continues until x becomes 0.
3. s += x % 10: Adds the last digit of x to s.
4. x //= 10: Removes the last digit from x.
5. ans += s % 2 == 0: Increments ans if s is even.

Solution 2 (Python):

class Solution:
    def countEven(self, num: int) -> int:
        ans = num // 10 * 5 - 1
        x, s = num // 10, 0
        while x:
            s += x % 10
            x //= 10
        ans += (num % 10 + 2 - (s & 1)) >> 1
        return ans

This code first calculates the number of integers with an even digit sum up to the nearest multiple of 10 below num. Then it adjusts the count based on the remaining digits in num. The bitwise operations (& 1 and >> 1) are used for efficiency in checking parity and integer division by 2.

The other languages (Java, C++, Go, TypeScript) follow similar logic and structure as the Python solutions, adapting the syntax accordingly. The core algorithm remains the same.