Count Even Digits In Number

Question

I was asked to complete this CodeStepByStep problem. Here's a quick summary:

Write a function named count_even_digits that accepts two integers as parameters and returns the number of even-valued digits in the first number. An even-valued digit is either 0, 2, 4, 6, or 8. The second value represents how many digits the number has. The second value is guaranteed to match the number of digits in the first number.

For example, the number 8546587 has four even digits (the two 8s, the 4, and the 6), so the call count_even_digits(8346387, 7) should return 4.

You may assume that the values passed to your function are non-negative.

My implementation:

def count_even_digits(digit, nums):
    count = 0
    digits = str(digit)
    for i in range(nums):
        if int(digits[i]) % 2 == 0:
            count += 1

    return count

I'm looking for any feedback on my implementation, and how to make this code more efficient. It seems weird that I have to cast the num to a string, then look at each char, convert it to int, then determine if it's even. Having to cast (int => string => analyzing as char => int) seems unnecessary to me.

Answer 1

You should have a look at Loop like a native!. Explicitly iterating over the indices is usually not the best way to do something in Python. By directly iterating over the string representation of n you won't even need the second argument (and you should remove it if the assignment/defined interface would not require it). This will help you a lot later, when you start using generators or other iterables which are not indexable.

In addition, you can use the built-in sum together with the fact that bools are integers with True == 1 and False == 0 and a generator expression to make your function a lot shorter:

def count_even_digits(n, n_digits):
    """Return the number of digits of n which are even.
    Second argument (number of digits) is unused.
    """
    return sum(int(d) % 2 == 0 for d in str(n))

I also added a docstring describing what the function does.

---

An alternative that does not use the casting to str is to make a digits function:

def digits(n):
    """Yields the digits of `n`, from smallest to largest."""
    while n > 10:
        n, d = divmod(n, 10)
        yield d
    yield n

def count_even_digits2(n, n_digits):
    return sum(d % 2 == 0 for d in digits(n))

---

Timing wise, these two solutions are both very fast, but the conversion to str stays faster, now tested up to 10**308. I also added the functions shown in the answer by @vurmux and the answer by @spyr03, which are even faster than these two solutions:

Interestingly the manual for loop is faster than the generator expression with sum.

---

For numbers with a lot of digits, it becomes a bit more complicated. This includes a function proposed in an answer to my question on SO about why the for loop is better than the sum. This function is even faster, but I would only recommend using it if you need that last bit of speed.

def count_even_digits_count_unrolled(n):
    s = str(n)
    return s.count("0") + s.count("2") + s.count("4") + s.count("6") + s.count("8")

Answer 2

As mentioned in another answer, iterating with indices in Python in most cases is a bad idea. Python has many methods and modules to avoid it. For your problem Python has powerful decimal module to work with decimal numbers. Here is how it can solve your problem:

from decimal import *

def count_even(number, length):
    return sum(
        d % 2 == 0
        for d in Decimal(number).as_tuple().digits
    )

Decimal(number).as_tuple().digits will return a tuple of digits of number:

Decimal(123456).as_tuple().digits -> (1, 2, 3, 4, 5, 6)

---

P.S. This solution doesn't use the length of the number, it doesn't need it. decimal module do the whole work.

Answer 3

Since you are dealing with digits, you at some point must pick a base (in this case base 10). So converting the number to a string is not a bad way of getting the digits. I would keep it simple, and just check each digit and see if it is one of the digits you want.

# Incorporating the other suggestions to loop over the chars directly rather than using an index
def count_even_digits(n, n_digits):
    count = 0
    for c in str(n):
        if c in "02468":
            count += 1
    return count

You could follow up with the other suggestion to use the built-in sum,

def count_even_digits(n, n_digits):
    return sum(c in "02468" for c in str(n))

Using either of these approaches have the advantage that you only do the conversion from int => str, rather than (implicit for decimal) int => str => int.

Answer 4

The point of this answer is to illustrate that the most efficient way to do things in other languages can be different from Python, and in this case is. IDK if this different low-level perspective on the problem is a good code-review answer, but putting it here in case people find it interesting.

---

In an efficient compiled language, all that casting to string, char, and int that you find strange would be inefficient. The reason to do that in Python is to get access to an efficient compiled C loop for breaking down a number into its base 10 digits, using str()¹. Presumably this will be well optimized because it's something that gets a lot of use in real programs.

In a compiled language you would just do repeated division / modulo by 10 to get decimal digits one at a time (LSD first), and add up their low bits as you go. Or since you want the count of digits that have their low bit = 0 (even numbers), count odds and subtract from the total count outside the loop. Or since our caller gives us the total digit count for no apparent reason (we'll find that out anyway when generating the decimal digits), we can take advantage and count down from that and save 1 operation inside the loop.

e.g. in C (assuming fixed-width integers, not like Python's arbitrary-precision integers which can have more than one 32-bit chunk):

// unsigned division by a constant is more efficient, and the number is non-negative
int count_evens(unsigned x, int ndigits) {
    int count = ndigits;   // we don't need the caller to tell us how many decimal digits
                           // but take advantage if we have it.
    do {
        count -= (x%10) & 1;    // remove odd digits from the count
        x /= 10;                // remove the least significant decimal digit
    } while (x!=0);
    return count;
}

(This is written to "optimistically" not bother checking x==0 before the first iteration, because running 1 iteration of the loop instead of zero still gives the right answer in that special case. Leaving out the check runs fewer instructions for the common(?) case, non-zero inputs. Thinking about the ideal asm you want while writing in C is optional, but I enjoy it.)

---

Fun fact: C compilers won't actually use an integer-division instruction, because 10 is a compile-time constant. They'll use a multiplicative inverse which is much more efficient on modern CPUs. So writing the loop this way is probably only good in C or other compiled languages, not Python.

Fun fact #2: gcc spotted an optimization I didn't think of when compiling for x86-64 and AArch64 on the Godbolt compiler explorer: x%10 is redundant. If x%10 is odd, so is x. Because 10 is a multiple of 2. So it only needs to check the low bit of x, not actually calculate the remainder from the quotient & divisor. (The fixed-point multiplicative-inverse trick only gives you the quotient, remainder is separate.)

---

Also GCC loops on x>=9 from before the division, so out-of-order execution can detect the loop-end condition sooner. Using while(--ndigits) would maybe have helped let CPUs figure out when the loop ends and reduce / avoid a branch mispredict penalty for the last loop iteration.

But it's kind of silly because there's no way for the caller to know how many decimal digits without having either done some of the work of this function (or maybe just comparing against powers of 10), or have converted it from a decimal string.

If the caller ever had a decimal string, counting odd/even digits in that would have been much more efficient. e.g. if it was 8 digits long, in asm you could load all 8 bytes with one load, AND with 0x0101010101010101 and popcnt to horizontally sum those bytes. (For variable length, you could do a wide load and use a shift to shift out bytes whose value isn't part of the string.)

---

Footnote 1:

Python supports integers much larger than 2^32. It stores them in a base 2^30 format, in 32-bit chunks. (https://rushter.com/blog/python-integer-implementation/)

A base 10^9 format would allow more efficient division by (powers of) 10, and especially converting to decimal could process each 32-bit chunk separately into 9 decimal digits, doing only 32-bit divisions.

But 2^30 allows more efficient left/right shifts. And efficient conversion to/from native C 64-bit integers!

Either way, using something less than the full width of a 32-bit integer makes it much easier to implement add-with-carry (carry-in and carry-out) in pure C. But means that the optimal asm is significantly worse on machines that do have add-with-carry instructions, especially 64-bit machines which can operate on 64-bit chunks.

Anyway, actual division by 10 of the whole number has to look at all the higher bits, because 10 isn't a power of 2. I'm not sure if there are any good tricks that str() could or does use, but it's not surprising that divmod by 10 in a Python loop isn't very efficient.

Answer 5

You could use the python lambda function

count_even_digits= lambda x,y:len([i for i in str(x) if int(i)%2==0])
count_even_digits(n,n_digits)

This creates a lambda(inline) function that takes two inputs x and y and performs a list comprehension that extracts digits from the input number(x) if they are even and then returns the length of this list which is the number of even digits.