for 문을 사용하지 않고 홀수의 개수 구하기

수의 성질을 이용하여 두 정수의 사이에 있는 홀수의 개수 구하기

반복문을 사용할 경우 생기는 문제

 일반적으로 for 반복문을 이용해 범위 안에 있는 모든 숫자를 세는 방법을 많이 사용하지만 수의 범위가 너무 넓을 경우 시간이 지나치게 오래 걸리는 문제가 생긴다.

대안

 따라서 정수로 시작값과 끝값이 정해진 경우에는 홀수의 개수를 구할 수의 성질을 이용해서 간단한 사칙연산으로 두 수 사이의 정수를 구할 수 있다. 어려울 것 같지만 굉장히 간단하다.

전제

 수의 범위는 시작값은 포함하지 않고 끝값은 포함하는 것으로 전제한다. 시작값은 초과하고 끝값의 이하이다. 예를 들어 3과 8이 주어졌다면 홀수를 찾은 값의 범위는 4, 5, 6, 7, 8이 되고 범위에 있는 수의 개수 N은 5가 된다. 즉, 끝값 - 시작값이 N이 된다.

대안 상세

1. 시작값과 N의 수가 짝수인지 홀수인지 여부를 판별한다.
2. N이 홀수라면 짝홀이란 건 늘 한 쌍이므로 N이 홀수일 때 시작값 + 1부터 하나씩 홀짝을 쌍으로 세어 나가다 보면 짝을 지을 수 없는 마지막 하나인 나머지 수가 남는다. 이 남는 값이 홀수일수도 있고 짝수일 수도 있다. 
3. 이 전제의 경우 시작값이 홀수일 경우 N이 홀수라면 짝홀, 짝홀을 반복하다 마지막에 짝수 하나가 나머지로 남는다. 시작값이 짝수라면 반대로 홀수 하나가 나머지로 남는다. 홀수의 개수는 N//2+1이 된다.
4. N이 짝수라면 시작값이 짝수일 때는 홀짝으로 쌍을 나워 세웠을 때 나머지로 남는 수가 없지만 홀수라면 나머지로 남는 수가 생긴다. 짝수 + 짝수 = 짝수, 짝수 + 홀수 = 홀수라는 공식을 떠올리면 쉽다. N이 짝수일 때 시작값이 짝수라면 홀수의 개수는 N//2, 시작값이 홀수라면 홀수의 개수는 N//2+1이 된다.
5. 홀수의 개수가 N//2가 되는 경우와 N//2+1이 되는 경우를 나누어 구현한다.

실제코드

def countOdds(self, low: int, high: int) -> int:
    n = high - low
    if low%2 == 0 and n%2 == 0:
        return n//2
    else:
        return n//2+1

정리

• 시작값이 짝수이고 범위 안의 숫자 N이 짝수라면 홀수의 개수는 N//2이다.
• 그 외의 경우에는 홀수의 개수가 N//2 + 1이다.