Scale Engineer

Count Odd Numbers in an Interval Range

Easy
#1404Time: 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: O(1). We only use a constant amount of extra memory for the counter and loop variable, regardless of the input range size.
Patterns
Math

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1). We only use a constant amount of extra memory for the counter and loop variable, regardless of the input range size.

Trade-offs

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).

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem