Problem

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

Examples

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

Solution

Method 1 - Mathematics

We can look at example 1. As both low and high are odds, we can see that number of odd numbers is (high - low) / 2 + 1. But both low and high may not be odd.

So, to count the number of odd numbers between two non-negative integers low and high (inclusive), we can adjust low and high to target odd numbers, then calculate the count based on the adjusted range.

Approach

  1. Adjust low and high:

    • If low is even, increment it by 1 to make it the next odd number (if it is not already an odd number).
    • If high is even, decrement it by 1 to make it the previous odd number (if it is not already an odd number).

  2. Calculate the Count:

    • Use the formula for counting odd numbers between two odd numbers (inclusive), which is (high - low) / 2 + 1
    • This formula works because every pair of consecutive numbers contains exactly one odd number.

Code

Java
public class Solution {

	public int countOdds(int low, int high) {
		// Adjust low to the next odd number if it is even
		if (low % 2 == 0) {
			low++;
		}
		// Adjust high to the previous odd number if it is even
		if (high % 2 == 0) {
			high--;
		}
		// Calculate the count of odd numbers
		if (low > high) {
			return 0; // No odd numbers in the range
		}

		return (high - low) / 2 + 1;
	}
}

Complexity

  • Time: O(1)
  • Space: O(1)

Method 2 - Count from start

Another way to find the count is we can start counting from number 1 to low and high.

Approach

  1. Total odd number between 1 and low - 1 is low/2. For eg. low = 3 ⇨ 1 ([1]), low = 4 ⇨ 2 ([1, 3]). Lets call it A.
  2. Total odd number between 1 and high is (high + 1 ) / 2. For eg. high = 7 ⇨ 4 ([1, 3, 5, 7]) OR high = 8 ⇨ 4 ([1, 3, 5, 7]). Lets call it B.
  3. For answer i.e. odd numbers between [low, high] = B - A.

Code

Java
public class Solution {

	public int countOdds(int low, int high) {
		return (high + 1) / 2 - low / 2;
	}
}

Complexity

  • Time: O(1)
  • Space: O(1)