1523. Count Odd Numbers in an Interval Range - Explanation

Description

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

Example 1:

Input: low = 2, high = 9

Output: 4

Explanation: The odd numbers between 2 and 9 are [3,5,7,9].

Example 2:

Input: low = 9, high = 11

Output: 2

Explanation: The odd numbers between 9 and 11 are [9,11].

Example 2:

Input: low = 1, high = 1

Output: 1

Constraints:

0 <= low <= high <= 1,000,000,000

Topics

Math

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Bit Manipulation Basics - Using bitwise AND to check if a number is odd
Integer Division - Understanding how floor division affects counting calculations
Range Counting - Computing counts in a range by subtracting prefix counts

1. Brute Force

Intuition

The simplest approach is to iterate through every number in the range and check if it is odd. We count all numbers where the least significant bit is 1.

Algorithm

Initialize a counter for odd numbers.
Loop through every integer from low to high (inclusive).
For each number, check if it is odd using bitwise AND with 1.
If odd, increment the counter.
Return the final count.

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        odd = 0
        for num in range(low, high + 1):
            if num & 1:
                odd += 1
        return odd

public class Solution {
    public int countOdds(int low, int high) {
        int odd = 0;
        for (int num = low; num <= high; num++) {
            if ((num & 1) == 1) {
                odd++;
            }
        }
        return odd;
    }
}

class Solution {
public:
    int countOdds(int low, int high) {
        int odd = 0;
        for (int num = low; num <= high; num++) {
            if (num & 1) {
                odd++;
            }
        }
        return odd;
    }
};

class Solution {
    /**
     * @param {number} low
     * @param {number} high
     * @return {number}
     */
    countOdds(low, high) {
        let odd = 0;
        for (let num = low; num <= high; num++) {
            if (num & 1) {
                odd++;
            }
        }
        return odd;
    }
}

public class Solution {
    public int CountOdds(int low, int high) {
        int odd = 0;
        for (int num = low; num <= high; num++) {
            if ((num & 1) == 1) {
                odd++;
            }
        }
        return odd;
    }
}

class Solution {
    fun countOdds(low: Int, high: Int): Int {
        var odd = 0
        for (num in low..high) {
            if (num and 1 == 1) {
                odd++
            }
        }
        return odd
    }
}

class Solution {
    func countOdds(_ low: Int, _ high: Int) -> Int {
        var odd = 0
        for num in low...high {
            if num & 1 == 1 {
                odd += 1
            }
        }
        return odd
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Where $n$ is the number of integers in the given range.

2. Math

Intuition

In any range of consecutive integers, odd and even numbers alternate. In a range of length n, there are n/2 odd numbers if n is even. If n is odd, the count depends on whether the range starts with an odd number. Starting with odd gives one extra odd number.

Algorithm

Calculate the length of the range: high - low + 1.
The base count of odd numbers is length / 2.
If the length is odd and the starting number (low) is odd, add 1 to include the extra odd.
Return the count.

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        length = high - low + 1
        count = length // 2
        if length % 2 and low % 2:
            count += 1
        return count

public class Solution {
    public int countOdds(int low, int high) {
        int length = high - low + 1;
        int count = length / 2;
        if (length % 2 == 1 && low % 2 == 1) {
            count++;
        }
        return count;
    }
}

class Solution {
public:
    int countOdds(int low, int high) {
        int length = high - low + 1;
        int count = length / 2;
        if (length % 2 == 1 && low % 2 == 1) {
            count++;
        }
        return count;
    }
};

class Solution {
    /**
     * @param {number} low
     * @param {number} high
     * @return {number}
     */
    countOdds(low, high) {
        let length = high - low + 1;
        let count = Math.floor(length / 2);
        if (length % 2 === 1 && low % 2 === 1) {
            count++;
        }
        return count;
    }
}

public class Solution {
    public int CountOdds(int low, int high) {
        int length = high - low + 1;
        int count = length / 2;
        if ((length % 2 == 1) && (low % 2 == 1)) {
            count++;
        }
        return count;
    }
}

class Solution {
    fun countOdds(low: Int, high: Int): Int {
        val length = high - low + 1
        var count = length / 2
        if (length % 2 == 1 && low % 2 == 1) {
            count++
        }
        return count
    }
}

class Solution {
    func countOdds(_ low: Int, _ high: Int) -> Int {
        let length = high - low + 1
        var count = length / 2
        if length % 2 == 1 && low % 2 == 1 {
            count += 1
        }
        return count
    }
}

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

3. Math (One Liner)

Intuition

The count of odd numbers from 1 to n is (n + 1) / 2 (or equivalently (n + 1) >> 1). To find odd numbers in range [low, high], we take the count up to high and subtract the count below low. The count below low equals the count up to (low - 1), which is low / 2 or low >> 1.

Algorithm

Compute the number of odd integers from 1 to high: (high + 1) >> 1.
Compute the number of odd integers from 1 to (low - 1): low >> 1.
Subtract the second from the first to get odds in [low, high].
Return the result.

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

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

Common Pitfalls

Off-by-One with Range Boundaries

When the range length is odd, whether you get an extra odd number depends on whether low (or high) is odd. Forgetting to check this boundary condition leads to undercounting by 1.

Using Division Without Considering Endpoints

Simply computing (high - low) / 2 ignores whether the range starts or ends on an odd number. The formula must account for the parity of the boundaries, not just the length.