Abstract / Summary

Count how many odd numbers are between two given numbers inclusive.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 55% (1+ million submissions).

Typical patterns to solve this problem:

• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The countOdds method computes how many odd integers lie in the inclusive range [low, high]. It does so with a small amount of arithmetic and a couple of bit-wise checks, guaranteeing a single pass over the numeric interval without any loops or recursion. The implementation is compact, deterministic, and works for any pair of non-negative integers where low is less than or equal to high.

Core Logic

The function begins by handling the degenerate case where the interval consists of a single number.

if (low == high)
    return low & 1;

The expression low & 1 extracts the least-significant bit, yielding 1 when low is odd and 0 otherwise. This single-line return instantly resolves the answer for a range of length one.

When the interval contains more than one element, the algorithm proceeds to normalize the bounds so that both become even. Two separate blocks adjust low and high if they are odd, while simultaneously counting the odd numbers that have been removed from the ends of the range.

auto result = 0;
if (low & 1)
{
    low++;
    result++;
}
if (high & 1)
{
    high--;
    result++;
}

If low is odd, it is incremented to the next even integer and the counter result is increased by one, reflecting the odd number that has just been accounted for. The same pattern applies to high when it is odd, decrementing it to the preceding even integer and adding one to result.

At this point both low and high are guaranteed to be even, and any odd numbers that were originally at the boundaries have already been tallied. The remaining interval [low, high] now contains only even numbers at its ends, which means the odd numbers are perfectly interleaved with the evens. The count of those interior odds can be derived from the distance between the adjusted bounds.

return result + (high - low) / 2;

The difference high - low represents the total span of the even-adjusted interval. Dividing by two yields the number of odd positions inside that span because every second integer is odd. Adding this to the previously accumulated result gives the final count.

Edge-Case Handling

The code explicitly addresses the situation where low equals high. In that scenario the early return avoids any further arithmetic that could otherwise produce an incorrect result (for example, the subtraction high - low would be zero, and the subsequent division would miss the single odd value if present).

When low is odd, the increment low++ moves the lower bound to the next even integer, ensuring that the subsequent arithmetic works on an even-aligned range. The same logic applies when high is odd, with high-- moving the upper bound down to an even number. These adjustments guarantee that the interior calculation (high - low) / 2 always operates on an interval whose endpoints are even, which simplifies the derivation of the interior odd count.

If both low and high are even from the start, the conditional blocks are bypassed, leaving result at zero. The interior formula then directly computes the number of odds between the two even bounds.

Performance Characteristics

The implementation runs in constant time because it performs a fixed number of operations regardless of the size of the input interval. The use of bitwise & 1 to test oddness is a low-cost operation on modern processors. Adjusting the bounds with simple increments or decrements avoids any looping constructs, and the final arithmetic expression (high - low) / 2 is a single integer division.

All intermediate values are stored in primitive integer types, eliminating any heap allocation or additional data structures. This minimal memory footprint contributes to the overall efficiency, making the function suitable for performance-critical contexts where it may be invoked repeatedly.

The algorithm also benefits from branch predictability: the two if statements each test a single bit, and the subsequent paths are straightforward, allowing modern CPUs to predict and execute them with minimal pipeline disruption.

Overall, the method delivers a fast, deterministic count of odd numbers in any inclusive integer range using only elementary arithmetic and bitwise operations.

Imagine you have a big box of numbered blocks starting from a low number and going up to a high number. The goal is to count how many of these blocks have an odd number written on them. An odd number is any number that ends in one, three, five, seven, or nine.

First, the code checks if the low number and the high number are the same. If they are, it just looks at that one number to see if it is odd. If the range has more than one number, the code starts a counter at zero. It looks at the low number first. If the low number is odd, it marks it down by adding one to the counter and then moves to the next number. Then it looks at the high number. If that one is odd, it marks it down by adding one to the counter and then moves back to the number right before it.

After dealing with the two ends, every single pair of numbers left in the middle will have exactly one odd number and one even number in it. Because of this, the code takes the remaining distance between the new low and high numbers and divides it by two to count those extra odd numbers. Adding all these pieces together gives the total count of every odd number in the whole set.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python										TS
	WalkCCC	C++
	leetcode.ca	C++	Java	Python						C	Go	PHP	Rust	TS
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	DimitrisJim									C
	everthis				JS
	fartem							Ruby
	FelixFan1122		Java
	fsq	C++
	haoel	C++
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007			Python
	martianoff						Scala
	muhammadfarhankt					SQL
	suxrobGM								C#
	trung-hn			Python
	varunu28		Java
	vthwang		Java
	withaarzoo	C++
	YuriSpiridonov			Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++
leetcode.ca	C, C++, Go, Java, PHP, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	Java
fsq	C++
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
martianoff	Scala
muhammadfarhankt	SQL
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
withaarzoo	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality