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

https://leetcode.com/

TITLE : 1523. Count Odd Numbers in an Interval Range

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

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

upper boundary 가 10^9 이므로, brute-force 로 순회하면서 홀수 개수를 세면 TLE 가 발생한다.

아래 세 가지 케이스로 부터 O(1) 풀이를 생각할 수 있다.

 

[1, 5] 의 경우 두 경계가 모두 홀수이다.

두 수 사이에 존재하는 숫자들의 개수(inclusive)는 5-1+1 = 5 개이고 이들 중 홀수의 개수는 5/2+1 = 3개이다.

 

[2,5] 의 경우 두 경계 중 하나는 짝수, 하나는 홀수이다.

두 수 사이에 존재하는 숫자들의 개수는 5-2+1 = 4 개이고 이들 중 홀수의 개수는 4/2 = 2 개이다.

 

[2,6] 의 경우 두 경계 모두 짝수이다.

두 수 사이에 존재하는 숫자들의 개수는 6-2+1 = 5개이고 이들 중 홀수의 개수는 5/2 = 2 개이다.

 

[C++]

class Solution {
public:
    int countOdds(int low, int high) {
        int cnt = high - low + 1;
        if(high %2 == 1 && low %2 == 1){
            // both odd
            return cnt/2+1;
        }
        else{
            return cnt/2;
        }
    }
};