Jobs

Interviews

Discussions

Count Odd Numbers in an Interval Range

Easy

Amazon

3 views

Given two non-negative integers low and high, write a function to efficiently count the number of odd numbers between low and high (inclusive).

Examples:

Input: low = 3, high = 7 Output: 3 Explanation: The odd numbers between 3 and 7 are [3, 5, 7]. The count is 3.
Input: low = 8, high = 10 Output: 1 Explanation: The odd numbers between 8 and 10 are [9]. The count is 1.
Input: low = 2, high = 6 Output: 2 Explanation: The odd numbers between 2 and 6 are [3,5]. The count is 2.
Input: low = 2, high = 3 Output: 1 Explanation: The odd numbers between 2 and 3 are [3]. The count is 1.

Constraints:

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

Your function should be optimized for both time and space complexity.

Count Odd Numbers in an Interval Range

Easy

Amazon

3 views

Given two non-negative integers low and high, write a function to efficiently count the number of odd numbers between low and high (inclusive).

Examples:

Input: low = 3, high = 7 Output: 3 Explanation: The odd numbers between 3 and 7 are [3, 5, 7]. The count is 3.
Input: low = 8, high = 10 Output: 1 Explanation: The odd numbers between 8 and 10 are [9]. The count is 1.
Input: low = 2, high = 6 Output: 2 Explanation: The odd numbers between 2 and 6 are [3,5]. The count is 2.
Input: low = 2, high = 3 Output: 1 Explanation: The odd numbers between 2 and 3 are [3]. The count is 1.

Constraints:

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

Your function should be optimized for both time and space complexity.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum and minimum possible values for `low` and `high`? This will help me understand the potential size of the range.
Could `low` ever be greater than `high`? If so, what should I return?
Are `low` and `high` guaranteed to be integers, or could they be floating-point numbers?
Is 0 considered an odd number in this context?
Are there any specific error conditions I should handle, such as null or invalid input?

Brute Force Solution

Approach

The simplest way to count odd numbers within a range is to check each number individually. We'll look at every number within the provided interval and determine if it's odd or not. Finally we add up the total count of odd numbers we've seen.

Here's how the algorithm would work step-by-step:

Start with the first number in the provided range.
Check if this number is odd. A number is odd if dividing it by two leaves a remainder of one.
If the number is odd, increase our running count by one.
Move on to the next number in the range.
Repeat the checking and counting process until you've examined all numbers within the range.
The final count represents the total number of odd numbers present in the interval.

Code Implementation

def count_odd_numbers_brute_force(low_number, high_number):
    odd_number_count = 0

    # Iterate through the numbers in the range
    for current_number in range(low_number, high_number + 1):

        # Check if the current number is odd
        if current_number % 2 != 0:
            # Increment the odd number count
            odd_number_count += 1

    return odd_number_count

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through each number within the given interval [low, high] to determine if it's odd. The input size, n, is effectively the number of integers in the range (high - low + 1). For each number, a constant-time operation (modulo 2) is performed to check for oddness. Therefore, the total number of operations is directly proportional to the size of the interval, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm, as described, uses a single integer variable to keep track of the running count of odd numbers. No additional data structures are created, and the memory used for this counter remains constant irrespective of the size of the interval. Therefore, the auxiliary space complexity is O(1), representing constant space.

Optimal Solution

Approach

The optimal approach finds the number of odd integers within a range by leveraging mathematical properties. We avoid checking each number individually by directly calculating the count based on the range's start and end points.

Here's how the algorithm would work step-by-step:

First, determine the total number of integers in the range by subtracting the start number from the end number and adding one.
Divide the total number of integers by two. This gives you an initial estimate of the number of odd numbers.
Consider the special case where both the start and end numbers are even. If this is true, then the initial estimate is correct.
However, if either the start or end number is odd (or both are odd), you'll need to add one to your initial estimate because one extra odd number exists.
The result is the count of odd numbers within the given range, calculated efficiently.

Code Implementation

def count_odd_numbers(low_number, high_number):
    number_of_integers = (high_number - low_number) + 1

    odd_number_estimate = number_of_integers // 2

    # Check if both numbers are even
    if low_number % 2 == 0 and high_number % 2 == 0:
        return odd_number_estimate

    #If either number is odd, increment the result
    else:
        odd_number_estimate += 1

    return odd_number_estimate

Big(O) Analysis

Time Complexity

O(1) – The algorithm performs a fixed number of arithmetic operations regardless of the input range. It calculates the number of integers, divides by two, and performs a conditional addition based on whether the start and end are even or odd. These operations take constant time. Therefore, the time complexity does not depend on the size of the input range, resulting in O(1) time complexity.

Space Complexity

O(1) – The provided approach calculates the number of odd integers using only a few variables to store the start number, end number, the total number of integers in the range, and the initial estimate of odd numbers. No additional data structures that scale with the input size (N) are created or used. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
low and high are equal and even	Return 0 since the single number in the range is not odd.
low and high are equal and odd	Return 1 since the single number in the range is odd.
low and high are consecutive even numbers	Return 0 because there are no odd numbers between two consecutive even numbers.
low and high are consecutive odd numbers	Return 2 because the range includes both odd numbers.
low is even and high is odd	The number of odd numbers is (high - low) / 2 + 1.
low is odd and high is even	The number of odd numbers is (high - low) / 2 + 1.
low and high are both even	The number of odd numbers is (high - low) / 2.
low and high are both odd	The number of odd numbers is (high - low) / 2 + 1.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum and minimum possible values for `low` and `high`? This will help me understand the potential size of the range.
Could `low` ever be greater than `high`? If so, what should I return?
Are `low` and `high` guaranteed to be integers, or could they be floating-point numbers?
Is 0 considered an odd number in this context?
Are there any specific error conditions I should handle, such as null or invalid input?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the first number in the provided range.
Check if this number is odd. A number is odd if dividing it by two leaves a remainder of one.
If the number is odd, increase our running count by one.
Move on to the next number in the range.
Repeat the checking and counting process until you've examined all numbers within the range.
The final count represents the total number of odd numbers present in the interval.

Code Implementation

def count_odd_numbers_brute_force(low_number, high_number):
    odd_number_count = 0

    # Iterate through the numbers in the range
    for current_number in range(low_number, high_number + 1):

        # Check if the current number is odd
        if current_number % 2 != 0:
            # Increment the odd number count
            odd_number_count += 1

    return odd_number_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, determine the total number of integers in the range by subtracting the start number from the end number and adding one.
Divide the total number of integers by two. This gives you an initial estimate of the number of odd numbers.
Consider the special case where both the start and end numbers are even. If this is true, then the initial estimate is correct.
However, if either the start or end number is odd (or both are odd), you'll need to add one to your initial estimate because one extra odd number exists.
The result is the count of odd numbers within the given range, calculated efficiently.

Code Implementation

def count_odd_numbers(low_number, high_number):
    number_of_integers = (high_number - low_number) + 1

    odd_number_estimate = number_of_integers // 2

    # Check if both numbers are even
    if low_number % 2 == 0 and high_number % 2 == 0:
        return odd_number_estimate

    #If either number is odd, increment the result
    else:
        odd_number_estimate += 1

    return odd_number_estimate

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
low and high are equal and even	Return 0 since the single number in the range is not odd.
low and high are equal and odd	Return 1 since the single number in the range is odd.
low and high are consecutive even numbers	Return 0 because there are no odd numbers between two consecutive even numbers.
low and high are consecutive odd numbers	Return 2 because the range includes both odd numbers.
low is even and high is odd	The number of odd numbers is (high - low) / 2 + 1.
low is odd and high is even	The number of odd numbers is (high - low) / 2 + 1.
low and high are both even	The number of odd numbers is (high - low) / 2.
low and high are both odd	The number of odd numbers is (high - low) / 2 + 1.