[LeetCode] 1523. Count Odd Numbers in an Interval Range

- Problem

1523. Count Odd Numbers in an Interval Range

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

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

---

Constraints:

• 0 <= low <= high <= 10^9

- 내 풀이 (Brute-force, TLE)

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        return sum(i%2 for i in range(low, high+1))

- 결과

• 시간 복잡도: O(N)
• 공간 복잡도: O(1)

완전 탐색으로 접근해 주어진 인자를 순회하며 홀수를 판단하는 방법이다.

그러나, 만약 최악의 케이스인 low=0, high=10^9로 주어진다면, 0부터 1_000_000_000까지 10억 번의 연산이 필요하다.

• 위의 케이스는 약 1300만 번의 연산이다. 이것만으로도 시간 초과가 발생한다.

즉, TLE가 안나기 위해서는 수학적인 규칙을 찾아서 접근해야 한다.

---

- 내 풀이 (Math)

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        return (high - low) // 2 + (low % 2 or high % 2)

혹은

        return ceil((high - low) / 2) + ((low % 2) & (high % 2))

- 결과

• 시간 복잡도: O(1)
• 공간 복잡도: O(1)