We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Integers With Even Digit Sum

Number: 2298

Difficulty: Easy

Paid? No

Companies: MindTree

Problem Description

Given a positive integer num, return the number of positive integers less than or equal to num whose digit sums are even. The digit sum of an integer is the sum of all its digits.

Key Insights

  • Iterate through every integer from 1 to num.
  • Compute the digit sum by repeatedly extracting the last digit and reducing the number.
  • Check if the digit sum is even.
  • Count numbers with even digit sums and return the count.
  • Given the constraint (1 <= num <= 1000), a straightforward simulation is efficient.

Space and Time Complexity

Time Complexity: O(num * d) where d is the number of digits in each integer (constant given the constraints)
Space Complexity: O(1)

Solution

We use a simple iterative approach. For each integer from 1 to num, calculate the sum of its digits using a helper function. This helper function extracts each digit using modulus and integer division. If the resulting sum is even, we increment our counter. Finally, the counter value is returned. The data structure used is just a counter variable, and the algorithm is a basic simulation that leverages arithmetic operations.

Code Solutions

def count_even_digit_sum(num):
    # Helper function to calculate the sum of digits of n
    def digit_sum(n):
        total = 0
        while n > 0:
            total += n % 10  # Extract the last digit and add to total
            n //= 10         # Remove the last digit
        return total
    
    count = 0
    # Iterate over every number from 1 to num
    for i in range(1, num + 1):
        if digit_sum(i) % 2 == 0:  # Check if the digit sum is even
            count += 1
    return count

# Example usage:
print(count_even_digit_sum(30))  # Expected output: 14
← Back to All Questions