-2

This question was in Leetcode to find odd numbers between an interval(inclusive).

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

One of the efficient codes are:

class Solution(object):
     def countOdds(self, low, high):
        high = high + 1
        c = high/2 - low/2
        return c

What I do not understand is how does the code return 1 as an answer when the input is low = 8 and high =10. Shouldn't the answer have been 1.5? I do not understand what specifically makes the code round the value of 'c' to the lowest whole number.

Mechanic Pig
  • 6,756
  • 3
  • 10
  • 31
Astro
  • 1
  • 2

1 Answers1

0

This definitely would not work for low > high. Also I expect that this is Python 2, so in Python # 3 we would need to use //

Does it work in other cases

For low < high we can prove correctness by splitting the proof to pairs (low, high) being (even, even), (even, odd), (odd, even), (odd, odd).

Used notations and equations

k,l are some integers.

Every even number can be written as 2k for some integer k.

Every odd number can be written as 2k + 1 for some integer k.

There are high - low + 1 numbers between low and high including bounds.

For integer division it holds 2k // 2 = (2k + 1) // 2 = k for any integer k.

(odd, even), (even, odd)

In this case we have regular sequence of (odd, odd+1 = even) or (even, even+1 = odd). Number of odd numbers is half of all (high - low + 1) / 2

The program is not so symmetric:

(even, odd)

Let high = 2k + 1 and low = 2l for some integer k and l.

c = (high + 1) // 2 - low // 2, where // denotes integral division.

Expressing parity with integers k and l and using integral division:

c = (2k + 1 + 1) // 2 - (2l) // 2 = k - l + 1

Comparing with (high - low + 1) / 2

(2k + 1 - 2l + 1) / 2 = k - l + 1

(odd, even)

c = (high + 1) // 2 - low // 2 = (2k + 1) // 2 - (2l + 1) // 2 = k - l

Comapring with (high - low + 1) / 2

(2k - (2l + 1) + 1) = k - l

(even, even)

It is the same number of odd numbers as for (even, even - 1) which is (even, odd) case and the count is then (high - low) / 2

Let high = 2k and low = 2l for some integer k and l. The program returns:

c = (2k + 1) // 2 - (2l) // 2 = k - l

Comparing with (high - low) / 2

(2k - 2l) / 2 = k - l

(odd, odd)

It is the same number of odd numbers as for (odd, odd + 1) which is (odd, even) case and the count is then (high - low + 2) / 2 = (high - low) / 2 + 1

Let high = 2k + 1 and low = 2l + 1 for some integer k and l. The program returns:

c = (2k + 2) / 2 - (2l + 1) / 2 = k - l + 1

Comparing with (high - low) / 2 + 1

(2k + 1 - 2l - 1) / 2 + 1 = k - l + 1

low = high

Even low = high

The correct answer is 0. The program returns

(2k + 1) // 2 - (2k) // 2 = 0

Odd low = high

The correct answer is 1. The program returns

(2k + 2) // 2 - (2k) // 2 = 1

Q.E.D

Roman Pavelka
  • 3,736
  • 2
  • 11
  • 28