algoadvance

Leetcode 1523. Count Odd Numbers in an Interval Range

Problem Statement

Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive).

Clarifying Questions

  1. Q: Are the low and high values inclusive? A: Yes, both low and high are inclusive.

  2. Q: Can low be greater than high? A: No, it is stated that low and high are non-negative integers and typically low will be less than or equal to high.

  3. Q: What is the expected range of values for low and high? A: The values can be anywhere from 0 to (10^9).

Strategy

  1. First, determine how to count the odd numbers within any arbitrary range.
  2. An individual number n is odd if n % 2 != 0.
  3. Check a few cases:
    • Both low and high are even.
    • Both low and high are odd.
    • One is even and the other is odd.
  4. Use arithmetic to derive a generic formula to count odd numbers between low and high.

Approach:

  1. Count the total number of integers between low and high which is (high - low + 1).
  2. Since every two consecutive numbers always have one odd number, divide the count by 2.
  3. Add an extra count if either low or high is odd since the inclusive range includes an additional odd number.

Implementation Steps:

  1. Calculate the total count of numbers in the range.
  2. Calculate the base number of odds by (high - low + 1) // 2.
  3. If either low or high is odd, add 1 to the base count.

Code

public class Solution {
    public int countOdds(int low, int high) {
        // Step 1: Count the total numbers in the range
        int totalNumbers = high - low + 1;
        
        // Step 2: Calculate the number of odd numbers
        int oddCount = totalNumbers / 2;

        // Step 3: Check if either low or high is odd
        if (low % 2 != 0 || high % 2 != 0) {
            oddCount++;
        }

        return oddCount;
    }
}

Time Complexity

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