1. 문제 소개

1523. Count Odd Numbers in an Interval Range

2. 나의 풀이

처음에는 range(low, high+1)까지 순회를 할까 생각했지만, high - low + 1 구간을 세는 것이 더 나은 것 같아 바꿔 풀었다.
시간복잡도는 $O(1)$이다.

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        ran = high - low + 1          # 전체 구간의 길이

        if ran % 2 == 0:              # 구간 길이가 짝수이면
            return ran // 2           # 홀수와 짝수가 정확히 절반씩 존재
        else:                         # 구간 길이가 홀수이면
            if low % 2 == 1:          # 시작점 low가 홀수라면
                return ran // 2 + 1   # 홀수가 하나 더 추가됨
            else:
                return ran // 2       # low가 짝수라면 홀수 개수는 절반

3. 다른 풀이

한 줄로도 풀 수 있다.
이것도 시간복잡도는 $O(1)$이다.

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        # (x + 1) // 2 는 1부터 x까지의 홀수 개수를 의미한다.
        # 예: x=5 → (5+1)//2 = 3  (1,3,5)
        #     x=6 → (6+1)//2 = 3  (1,3,5)
        #
        # 따라서,
        #   (high + 1) // 2  = 1 ~ high 구간 내 홀수 개수
        #   (low // 2)      = 1 ~ (low-1) 구간 내 홀수 개수
        #
        # 두 값의 차이는 바로 [low, high] 구간 내 홀수 개수가 된다.
        return (high + 1) // 2 - (low // 2)

4. 마무리

쉬운 문제였다. 그래도 더 최적화할 수 있는 방법이 있어서 좋았다.