Welcome to Subscribe On Youtube

2180. Count Integers With Even Digit Sum

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 a positive integer is the sum of all its digits.

 

Example 1:

Input: num = 4
Output: 2
Explanation:
The only integers less than or equal to 4 whose digit sums are even are 2 and 4.

Example 2:

Input: num = 30
Output: 14
Explanation:
The 14 integers less than or equal to 30 whose digit sums are even are
2, 4, 6, 8, 11, 13, 15, 17, 19, 20, 22, 24, 26, and 28.

 

Constraints:

  • 1 <= num <= 1000

Solutions

Solution 1: Direct Implementation

One of the simplest and most direct methods is to enumerate all the integers $x$ of $[1,..num]$ and determine whether the sum of the digits of $x$ is an even number. If so, add one to the answer.

Time complexity $O(n \times \log n)$, space complexity $O(1)$. Where $n$ is the value of $num$.

Solution 2

We observe that among all the numbers in $[0,..x]$, for every $10$ number, there are $5$ numbers whose sum of digits is an even number. For example, in $[0,..9]$, for every $10$ number, there are $5$ numbers whose sum of digits is an even number, which is $0,2,4,6,8$.

Therefore, we can first calculate how many multiples of $10$ there are in $num$, then multiply by $5$ and subtract $1$ (excluding the even number $0$) to get the initial answer $ans=\left\lfloor \frac{num}{10} \right\rfloor \times 5 - 1$.

Next, we also need to consider how many of the remaining $num \% 10 + 1$ numbers have an even number. Whether these numbers are even numbers is related to the sum of the previous digits of the number. Therefore, we can calculate the sum of the previous digits of $num$ $s$. Then among the remaining numbers, there are $\left\lfloor \frac{num \% 10 + 2 - (s \& 1)}{2} \right\rfloor$ numbers whose sum is an even number. Just add it to the answer $ans$.

Let us give an example, assuming that $num$ is $123$, then there are $12$ multiples of $10$ in the previous $[0,..119]$, and each multiple of $10$ has $5$ The sum of the digits of the number is even, so the initial answer is $ans=12 \times 5 - 1=59$.

The remaining numbers are $120,121,122,123$. The sum of the first two digits of each number is $s = 1+2=3$, which is an odd number. Therefore, among the remaining numbers, only the sum of the digits of $2$ is an even number, which is added to the answer $ans$. The final answer is $ans+2=61$.

Time complexity $O(\log n)$, space complexity $O(1)$. Where $n$ is the value of $num$.

  • class Solution {
    public int countEven(int num) {
        int ans = 0;
        for (int i = 1; i <= num; ++i) {
            int s = 0;
            for (int x = i; x > 0; x /= 10) {
                s += x % 10;
            }
            if (s % 2 == 0) {
                ++ans;
            }
        }
        return ans;
    }
}


// Solution 2
class Solution {
    public int countEven(int num) {
        int ans = num / 10 * 5 - 1;
        int s = 0;
        for (int x = num / 10; x > 0; x /= 10) {
            s += x % 10;
        }
        ans += (num % 10 + 2 - (s & 1)) >> 1;
        return ans;
    }
}


  • class Solution {
public:
    int countEven(int num) {
        int ans = 0;
        for (int i = 1; i <= num; ++i) {
            int s = 0;
            for (int x = i; x; x /= 10) {
                s += x % 10;
            }
            ans += s % 2 == 0;
        }
        return ans;
    }
};


// Solution 2
class Solution {
public:
    int countEven(int num) {
        int ans = num / 10 * 5 - 1;
        int s = 0;
        for (int x = num / 10; x > 0; x /= 10) {
            s += x % 10;
        }
        ans += (num % 10 + 2 - (s & 1)) >> 1;
        return ans;
    }
};


  • 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


# Solution 2
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


  • func countEven(num int) (ans int) {
	for i := 1; i <= num; i++ {
		s := 0
		for x := i; x > 0; x /= 10 {
			s += x % 10
		}
		if s%2 == 0 {
			ans++
		}
	}
	return
}


// Solution 2
func countEven(num int) (ans int) {
	ans = num/10*5 - 1
	s := 0
	for x := num / 10; x > 0; x /= 10 {
		s += x % 10
	}
	ans += (num%10 + 2 - (s & 1)) >> 1
	return
}


  • function countEven(num: number): number {
    let ans = 0;
    for (let i = 1; i <= num; ++i) {
        let s = 0;
        for (let x = i; x; x = Math.floor(x / 10)) {
            s += x % 10;
        }
        if (s % 2 == 0) {
            ++ans;
        }
    }
    return ans;
}


// Solution 2
function countEven(num: number): number {
    let ans = Math.floor(num / 10) * 5 - 1;
    let s = 0;
    for (let x = Math.floor(num / 10); x; x = Math.floor(x / 10)) {
        s += x % 10;
    }
    ans += ((num % 10) + 2 - (s & 1)) >> 1;
    return ans;
}


  • class Solution {
    public int countEven(int num) {
        int ans = num / 10 * 5 - 1;
        int s = 0;
        for (int x = num / 10; x > 0; x /= 10) {
            s += x % 10;
        }
        ans += (num % 10 + 2 - (s & 1)) >> 1;
        return ans;
    }
}

  • class Solution {
public:
    int countEven(int num) {
        int ans = num / 10 * 5 - 1;
        int s = 0;
        for (int x = num / 10; x > 0; x /= 10) {
            s += x % 10;
        }
        ans += (num % 10 + 2 - (s & 1)) >> 1;
        return ans;
    }
};

  • 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


  • func countEven(num int) (ans int) {
	ans = num/10*5 - 1
	s := 0
	for x := num / 10; x > 0; x /= 10 {
		s += x % 10
	}
	ans += (num%10 + 2 - (s & 1)) >> 1
	return
}

  • function countEven(num: number): number {
    let ans = Math.floor(num / 10) * 5 - 1;
    let s = 0;
    for (let x = Math.floor(num / 10); x; x = Math.floor(x / 10)) {
        s += x % 10;
    }
    ans += ((num % 10) + 2 - (s & 1)) >> 1;
    return ans;
}

All Problems

All Solutions