Teaching Kids Programming – Count Odd Numbers in an Interval Range

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive).

Example 1:
Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

Example 2:
Input: low = 8, high = 10
Output: 1
Explanation: The odd numbers between 8 and 10 are [9].

Constraints:
0 <= low <= high <= 10^9

If the range (high – low + 1) is even, the number of even and odd numbers in this range will be the same.
If the range (high – low + 1) is odd, the solution will depend on the parity of high and low.

Count Odd Numbers in a Interval Range (Non-negative)

As the low and high are non-negative, we can use the range that gives a iterator, and then count it using inbuilt len function. We have to deal with the low being odd or even:

class Solution:
    def countOdds(self, low: int, high: int) -> int:        
        if low & 1: # odd number
            return len(range(low, high + 1, 2))
        return len(range(low + 1, high + 1, 2))

Mathematically, we can count the odds between [low, high] where low is odd:

class Solution:
    def countOdds(self, low: int, high: int) -> int:        
        def f(a, b):
            return (b - a)//2+1
        if low & 1: # odd number
            return f(low, high)
        return f(low + 1, high)   

The number of odds between [0, low – 1] is low // 2. And the number of odds between [0, high] is (high + 1) // 2 and thus:

The number of odds between [low, high] is:

(high + 1) // 2 - low // 2       

class Solution:
    def countOdds(self, low: int, high: int) -> int:        
        return (high + 1) // 2 - low // 2       

All algorithms are O(1) time and space – as we do not actually count.

If we want to actually count the number of odds and this will time out for sure:

class Solution:
    def countOdds(self, low: int, high: int) -> int:        
        if low & 1 == 0:
            low += 1
        ans = 0
        while low <= high:
            ans += 1
            low += 2
        return ans

As the time complexity is O(high – low) or O(N) where N is the number of odds in this range.

–EOF (The Ultimate Computing & Technology Blog) —