Count Odd Numbers in an Interval Range

EASY

Description

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

Approaches

Checkout 2 different approaches to solve Count Odd Numbers in an Interval Range. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach involves iterating through each number in the given range from low to high. For each number, we perform a check to see if it is odd. A counter is maintained to keep track of the total count of odd numbers found.

Algorithm

Initialize a counter variable count to 0.
Loop through each integer i from low to high (inclusive).
Inside the loop, check if i is odd using the modulo operator (i % 2 != 0).
If i is odd, increment count.
After the loop finishes, return count.

The algorithm is very straightforward:

Initialize a counter variable, count, to zero.
Create a loop that iterates from low to high, inclusive.
Inside the loop, for each number i, use the modulo operator (%) to check if it's odd (i % 2 != 0).
If the number is odd, increment the count.
After the loop completes, the count variable will hold the total number of odd integers in the range, which is then returned.

Here is the Java implementation:

class Solution {
    public int countOdds(int low, int high) {
        int count = 0;
        for (int i = low; i <= high; i++) {
            if (i % 2 != 0) {
                count++;
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(high - low). The time taken is directly proportional to the size of the interval. For large ranges (up to 10^9 as per constraints), this approach will be too slow and result in a Time Limit Exceeded (TLE) error.Space Complexity: O(1). We only use a constant amount of extra memory for the counter and loop variable, regardless of the input range size.

Pros and Cons

Pros:

Very simple to understand and implement.
Works correctly for small ranges.

Cons:

Highly inefficient for large ranges.
Will not pass the time constraints on most competitive programming platforms for this problem due to the large constraints (up to 10^9).

Code Solutions

Checking out 3 solutions in different languages for Count Odd Numbers in an Interval Range. Click on different languages to view the code.

class Solution { public int countOdds ( int low , int high ) { return (( high + 1 ) >> 1 ) - ( low >> 1 ); } }

Video Solution

Watch the video walkthrough for Count Odd Numbers in an Interval Range

Patterns:

Math