Teaching Kids Programming – Algorithms to Count Numbers with Odd Number of Digits

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of positive integers nums, return the number of integers that have odd number of digits.

Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [1, 800, 2, 10, 3]
Output
4
Explanation
[1, 800, 2, 3] have odd number of digits.

To solve this problem, we need to define a odd function that checks if a given positive integer being an odd number of digits. Then we can count them:

1
2
3
4
5
6
7
8
9

class Solution:
    def countOddDigitsNumber(self, nums):
        def odd(i):
            pass
        ans = 0
        for i in nums:
            if odd(i):
                ans += 1
        return ans

class Solution:
    def countOddDigitsNumber(self, nums):
        def odd(i):
            pass
        ans = 0
        for i in nums:
            if odd(i):
                ans += 1
        return ans

We can use one liner to count:

1

return [odd(i) for i in nums].count(True)

return [odd(i) for i in nums].count(True)

Iterating N digits means O(N) time.

Count Numbers with Odd Numbers of Digits by Converting to String

The easiest algorithm is to convert the integer to string and then count the number of characters, this works for zero as well. Time complexity is O(D) where D is the length of the number in digits.

1
2

def odd(i):
    return len(str(i)) & 1

def odd(i):
    return len(str(i)) & 1

To check if a number n is odd – we can do `return n&1==1` or `return n%2==1`. The “==1” can be omitted.

Odd Digits Check by Math Log10 Function

We can use math.log10 function (which offers higher accuracy than math.log(x, 10)) to count how many digits:

1
2

def odd(i):
    return int(math.log10(i) + 1) & 1

def odd(i):
    return int(math.log10(i) + 1) & 1

This does not work for input zero – which we have to handle separately.

Odd Digits Counting Algorithm by Division of 10

We can repeatedly remove the rightmost ones by dividing by ten and increment the counter until the value becomes zero. The number “zero” has 1 digit and thus needs to be checked first.

1
2
3
4
5
6
7
8

def odd(i):
    if i == 0:
        return 1
    a = 0
    while i > 0:
        a += 1
        i //= 10
    return a & 1

def odd(i):
    if i == 0:
        return 1
    a = 0
    while i > 0:
        a += 1
        i //= 10
    return a & 1

–EOF (The Ultimate Computing & Technology Blog) —