algoadvance

Leetcode 1523. Count Odd Numbers in an Interval Range

Problem Statement

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 = 3, high = 7 Output: 3 Explanation: The odd numbers between 3 and 7 are [3, 5, 7].

  2. Input: low = 8, high = 10 Output: 1 Explanation: The odd number between 8 and 10 is [9].

Clarifying Questions

  1. Are low and high always valid inputs such that low <= high?
    • Yes, the input will satisfy the given constraint.
  2. Are low and high inclusive in the range?
    • Yes, they are inclusive.

Assuming no other constraints or conditions are provided. Let’s move on to the strategy and code.

Strategy

To count the number of odd numbers between low and high inclusive:

  1. Calculate the number of odd numbers up to high.
  2. Calculate the number of odd numbers up to low - 1.
  3. The difference between these two counts will give the number of odd numbers between low and high inclusive.

Steps:

  1. We know that every second number is an odd number.
  2. For any integer n, the count of odd numbers from 1 to n inclusive is (n + 1) // 2.

Formula:

Therefore, the count of odd numbers between low and high inclusive: [ \text{count_odds} = \left(\frac{high + 1}{2}\right) - \left(\frac{low}{2}\right) ]

Code

#include <iostream>

int countOdds(int low, int high) {
    // Calculate the number of odd numbers up to high and low-1
    int odds_up_to_high = (high + 1) / 2;
    int odds_up_to_low_minus_one = low / 2;
    
    // The difference will give the result
    return odds_up_to_high - odds_up_to_low_minus_one;
}

int main() {
    // Example test cases
    std::cout << countOdds(3, 7) << std::endl; // Output: 3
    std::cout << countOdds(8, 10) << std::endl; // Output: 1
    
    return 0;
}

Time Complexity

The time complexity of the solution is O(1) (constant time) because the computations involved are basic arithmetic operations that take constant time regardless of the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI