1523. Count Odd Numbers in an Interval Range

Problem Description

In this problem, you are given two non-negative integers low and high. The task is to find and return the count of odd numbers that are between low and high (inclusive). In other words, you need to determine the number of odd numbers in the integer range starting from low to high, including both low and high if they happen to be odd.

Intuition

The intuition behind the solution lies in understanding how odd and even numbers are distributed in a range of integers. Consider any two consecutive numbers, one will always be even, and the other will be odd. Thus, in any range of integers, the count of odd and even numbers should be roughly equal.

However, the exact count may vary depending on the parity of low and high and whether the range includes an odd or even number of integers. The trick to solving this efficiently is to use a formula that captures this observation without having to iterate over each number in the range.

Here's how the solution is derived:

The number of integers in the range low to high (inclusive) can be given by high - low + 1.
For a range starting from 1 to a number n, the number of odd numbers can be calculated by (n + 1) // 2. This is because the sequence of odd and even numbers is regular, and half of the numbers up to n will be odd (plus one for odd n).
If low and high are both odd or both even, the ranges from 1 to low - 1 and 1 to high contain the same number of odd and even numbers. The difference of these two will give us the count of odd numbers between low and high.
If low is odd and high is even (or vice versa), then we have to adjust our calculation to ensure we count the extra odd or even number at the start of the range.

So, the formula ((high + 1) >> 1) - (low >> 1) does exactly this by effectively calculating the count of odd numbers from 1 to high and subtracting the count of odd numbers from 1 to low - 1. The >> 1 is a bit-shift operation that divides the number by 2, which is the same as using // 2 for integers but may be faster in certain contexts.

This results in a simple, efficient solution that exploits the pattern in which odd and even numbers occur within ranges.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1dp[i] = dp[i] + dp[i - 1]dp[i] = (dp[i] + dp[j] + 1) for j in 0 to idp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know

Solution Approach

The solution uses an efficient mathematical approach rather than brute-forcing through the range to count odd numbers. The key observations made about the distribution of odd and even numbers in a range are used to derive a simple formula. Here is a step-by-step breakdown of the implementation:

The expression (high + 1) >> 1 calculates the number of odd numbers from the range 1 to high. The term high + 1 adds one more count to facilitate the correct division by 2 (since we are interested in odd numbers). The bit-shift operation >> 1 is effectively dividing the value by 2.
Similarly, the expression (low >> 1) calculates the number of odd numbers in the range from 1 to low - 1. This works because low itself is not included and the bit-shift by one position to the right divides low by 2. If low is odd, subtracting one before division gives the correct count of odd numbers below low.
By subtracting the count of odd numbers below low from the count of odd numbers up to and including high, what remains is the count of odd numbers in the inclusive range between low and high.

The implementation relies on no other algorithms or data structures. No loops or recursive calls are used. It is a direct application of an arithmetic operation and a bit-shift, which are both O(1) time complexity operations. The efficiency of the solution is a result of the formula which uses the inherent pattern of alternating odd and even numbers.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

A graph is a special treeA tree is a special graphNo relationshipThey are the same thing

I don’t know

Example Walkthrough

Let's work through a small example to illustrate the solution approach. Consider the range of integers from low = 3 to high = 7. We want to count how many odd numbers there are between 3 and 7, inclusive.

Here are the numbers in the range: 3, 4, 5, 6, 7. The odd numbers are 3, 5, and 7. There are 3 odd numbers in this range.

Now let's use the solution approach to get the same result:

We calculate the number of odd numbers up to high with the expression (high + 1) >> 1. For high = 7, this gives us (7 + 1) >> 1, which is 8 >> 1. Bit-shifting 8 one position to the right is the same as dividing 8 by 2, which gives us 4. So there are 4 odd numbers from 1 to 7 inclusive.
We calculate the number of odd numbers before low with the expression (low >> 1). For low = 3, this gives us 3 >> 1, which is 1 when rounded down (as the bit-shifting operation inherently does for integers). So, there is 1 odd number in the range 1 to 2 (since low is not included).
We find the count of odd numbers between low and high by subtracting the count of odd numbers below low from the count of odd numbers up to high. In this case, we subtract 1 from 4 to get 3, which is the count of odd numbers in the range of 3 to 7 inclusive.

As evidenced by the example, the formula ((high + 1) >> 1) - (low >> 1) correctly calculates the number of odd numbers within a given range without the need for iterating over all elements in the range, which is much more efficient for larger ranges.

Using this approach with our example range from low = 3 to high = 7, we've demonstrated that there are indeed 3 odd numbers, matching our earlier manual count.

Solution Implementation

1class Solution:
2    def count_odds(self, low: int, high: int) -> int:
3        # Calculate the number of odds between two numbers low and high (inclusive).
4        # The formula ((high + 1) >> 1) calculates how many odd numbers are in
5        # the range from 0 to high inclusive by dividing the endpoint by 2 and
6        # rounding up, if necessary.
7        # Similarly, (low >> 1) calculates how many odd numbers there are from
8        # 0 up to but not including low.
9        # The difference between these two quantities gives the count of odd numbers
10        # in the range [low, high].
11        return ((high + 1) >> 1) - (low >> 1)
12

1class Solution {
2    // Function to count the number of odd numbers between low and high (inclusive)
3    public int countOdds(int low, int high) {
4        // ((high + 1) >> 1) calculates the number of odd numbers from 1 to high
5        // (low >> 1) calculates the number of odd numbers from 1 to (low - 1)
6        // Subtracting the two gives the number of odd numbers between low and high
7        return ((high + 1) >> 1) - (low >> 1);
8    }
9}
10

1class Solution {
2public:
3    // Function to count the number of odd numbers within a given range.
4    int countOdds(int low, int high) {
5        // Calculate the number of odd numbers before 'high' and 'low'.
6        // Use bitwise right shift to divide by 2. Adding 1 to 'high' handles the case when 'high' is odd.
7        int oddsBeforeHigh = (high + 1) >> 1;
8        int oddsBeforeLow = low >> 1;
9
10        // The number of odd numbers within the range is the difference
11        // of the two calculated values.
12        int countOfOdds = oddsBeforeHigh - oddsBeforeLow;
13
14        // Return the count of odd numbers in the range.
15        return countOfOdds;
16    }
17};
18

1// This function counts the number of odd numbers in the range [low, high].
2// It leverages bitwise operations to efficiently perform the calculation.
3function countOdds(low: number, high: number): number {
4    // Increment the upper bound (`high`) by 1 and then shift it one bit to the right.
5    // This effectively divides `high + 1` by 2, rounding down to the nearest integer.
6    // This calculation returns the number of odd numbers from 0 up to `high`.
7    const oddCountUpToHigh: number = (high + 1) >> 1;
8
9    // Shift `low` one bit to the right to divide it by 2, rounding down to the nearest integer.
10    // This calculation returns the number of odd numbers from 0 up to `low - 1`.
11    const oddCountUpToLow: number = low >> 1;
12
13    // Subtract the number of odds up to `low - 1` from the number of odds up to `high`
14    // to get the count of odd numbers in the range [low, high].
15    return oddCountUpToHigh - oddCountUpToLow;
16}
17

Not Sure What to Study? Take the 2-min Quiz：

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayMerge sort does not use divide and conquer

I don’t know

Time and Space Complexity

The time complexity of the provided code is O(1). This is because the operations performed to calculate the number of odd numbers within the range — specifically, the additions, subtractions, and bit shifts — are constant time operations, regardless of the input size.

The space complexity of the code is also O(1). There are a fixed number of variables used, which does not scale with the input size, thus only a constant amount of memory is used.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1dp[i] = dp[i] + dp[i - 1]dp[i] = (dp[i] + dp[j] + 1) for j in 0 to idp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1523. Count Odd Numbers in an Interval Range

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings