algoadvance

You are given a positive integer num. Return the number of positive integers less than or equal to num whose digit sums are even.

Clarifying Questions

1. Input Constraints:
   • Is num always a positive integer?
     • Yes, num is always positive.
2. Range of num:
   • What is the range of num?
     • Typically, num can be any positive integer up to large values, but let’s focus on standard constraints where num could be up to (10^9).
3. Output:
   • Do we return the count of numbers whose digit sums are even?
     • Yes, return the count of numbers whose digit sums are even.

Code

def countEven(num: int) -> int:
    def is_even_digit_sum(n):
        return sum(int(digit) for digit in str(n)) % 2 == 0
    
    count = 0
    for i in range(1, num + 1):
        if is_even_digit_sum(i):
            count += 1
            
    return count

# Example Usage
num = 30
print(countEven(num))  # Output should be the count of numbers <= 30 with even digit sums

Strategy

1. Digit Sum Calculation:
   • Convert each number to a string to easily iterate over its digits.
   • Sum the digits and check if the sum is even.
2. Iteration:
   • Iterate through all numbers from 1 to num.
   • Use a helper function is_even_digit_sum to determine if the number’s digit sum is even.
3. Counting:
   • Maintain a counter to count how many numbers have even digit sums.

Time Complexity

• Time Complexity: (O(N \times d)), where (N) is the value of num and (d) is the number of digits in each number (approximately (\log_{10}(num))).
  • We iterate through all numbers from 1 to num (O(N)).
  • For each number, we sum its digits, which takes (O(d)).
• Space Complexity: (O(1)), aside from the input and a few counters and variables, we use constant extra space.

This approach is straightforward and sufficient for reasonably sized num. For larger values closer to (10^9), further optimizations or mathematical insights may be necessary to manage efficiency.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?