Leetcode – Count Odd Numbers in an Interval Range Solution

Spread the love

The problem “Count Odd Numbers in an Interval Range” on Leetcode is an excellent example of how a seemingly simple problem can be interesting from a computational perspective. This article aims to provide a comprehensive guide to the problem, taking you through various approaches to solve it, while analyzing time and space complexities.

Problem Statement

The problem requires you to count the number of odd numbers between low and high (both inclusive).

Example

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

The Brute-Force Approach

The first method that comes to mind is to iterate through all the numbers between low and high and count the odd numbers. Although this is not the most efficient solution, it’s a straightforward one.

Python Code:

def countOdds(low, high):
    count = 0
    for num in range(low, high + 1):
        if num % 2 != 0:
            count += 1
    return count

# Test the function
print(countOdds(3, 7))  # Output should be 3

Time Complexity

The time complexity for this approach is O(n), where n is the difference between high and low.

Space Complexity

The space complexity is O(1), as we are using a constant amount of space.

An Optimized Approach: Mathematical Calculation

We can solve this problem in a more efficient manner using mathematics. The number of odd numbers between two numbers can be directly calculated if we know the low and high values.

The formula to find the count of odd numbers between low and high can be:

Python Code:

import math

def countOdds(low, high):
    return math.ceil((high - low) / 2) + (low % 2) + (high % 2) - 1

# Test the function
print(countOdds(3, 7))  # Output should be 3

Time Complexity

The time complexity for this approach is O(1).

Space Complexity

The space complexity is O(1).

Edge Cases and Additional Considerations

  1. Negative Numbers: The function should also handle scenarios where low and high can be negative. The formula approach will still work.
  2. Single Value Range: If low and high are the same, the function should return 1 if it’s an odd number or 0 if it’s even.
  3. Zero Values: The function should return the correct value when low and/or high is zero.

Conclusion

The “Count Odd Numbers in an Interval Range” problem is an excellent starting point for anyone looking to grasp the importance of optimization in programming. We started with a brute-force approach that works but is not efficient. Then, we leveraged mathematical calculations to derive a formula that allows us to solve the problem in constant time.

Leave a Reply