개발자 Lim

조건:

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

의역: 두 정수를 포함한 사이의 홀 수의 개수를 반환하라.

풀이:

1. 단순 반복 (Time out)

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(1)
    public int countOddsFail(int low, int high) {
        int ans=0;
        for(int i=low;i<=high;i++){
            if(i%2==1) ans++;
        }
        return ans;
    }
}

2. 수학의 경우의 수 

class Solution {
    // 시간 복잡도 O(1) 공간 복잡도 O(1)
    public int countOdds(int low, int high) {
        if(low==high) return low%2==1?1:0;
        int ans = 0;

        if(low%2==0&&high%2==0){
            ans = (high-low)/2;
        }
        else if(low%2==1&&high%2==1){
            ans = (high-low)/2+1;
        }
        else{
            ans = (high-low-1)/2+1;
        }

        return ans;
    }
}

2-1 좀 더 최적화

class Solution {
    // 시간 복잡도 O(1) 공간 복잡도 O(1)
    public int countOddsOtimal(int low, int high){
        // low가 짝수라면 홀수로 바꾸기
        // 어차피 짝수는 no Count 이기 때문에 정답에는 영향을 미치지 않음
        if((low&1)==0){
            low++;
        }

        // 만약 low와 hight둘다 짝수였다면 0이 나오고 그것이 아니라면
        // 둘다 홀수 임으로 두 수 사이의 범위/2 +1 법칙이 성립
        return low>high?0:(high-low)/2+1;
    }
}

<메모>

최대한 나올 수 있는 경우의 수를 공통의 경우로 만들어 줄이자.