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

풀이 일자: 23.02.13

난이도: [Easy]

분류: [Math]

문제 내용

2개의 양수가 주어졌을 때 그 수들을 포함한 그 사이의 수들 중 홀수의 개수를 구하는 문제이다.

 

 

 

문제 해결 흐름

1. 별다른 알고리즘 보다는 어떤 수학적인 패턴을 찾아서 구해내는 것이 맞겠다.

→ 짝수부터 세는 경우  ( high - low )//2 + 1개의 홀수가 나온다.

 

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        if (low & 1) == 0:
            low += 1;
       
        return 0 if low > high else (high - low)// 2 + 1;

 

Time Complexity: O(1)

반복문 돌아가는 것 없이 계산만 진행하기에 O(1)이다.

 

Space Complexity: O(1)

주어진 파라미터 이외에 사용되는 것이 없기에 O(1)이다.

 

 

다른 해결 방식

수학적으로 푸는 방법이 출제자의 의도일 것이고 naive하게 푼다면 for문을 돌려서 홀수면 count하는 방식이 있을 것이지만 규칙성을 찾는다면 쉽게 파악할 수 있을 것이다.

 

 

문제 링크

https://leetcode.com/problems/count-odd-numbers-in-an-interval-range/description/

Count Odd Numbers in an Interval Range - LeetCode