[ 알고리즘 ] LeetCode 1523. Count Odd Numbers in an Interval Range

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 1523. Count Odd Numbers in an Interval Range를 풀고 작성한 글입니다.

문제

요구사항

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

제약사항

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

풀이

접근법

처음에 for 반복문 등을 활용해 O(N)의 시간 복잡도로 문제를 해결하려 하니 시간 초과가 발생했다.

이후 생각해보니 결국 범위 내에 존재하는 홀수 또는 짝수의 수는 시작 및 끝 값의 홀수, 짝수 여부에 따라 둘이 정확히 개수가 똑같거나 또는 한 쪽이 더 많은 형태였다.

따라서 범위의 절반을 기본 개수로 선정한 다음 만약 시작 값 또는 끝 값이 홀수일 경우 해당 개수에 하나만 더 늘려주면 된다.

나의 풀이

접근법을 토대로 문제를 해결하면 아래와 같다.

def solution(low: int, high: int) -> int:
	answer: int = (high-low) // 2
    if (high % 2) or (low % 2):
    	answer += 1
    return answer

시간 복잡도

이와 같이 문제를 풀 경우 별도의 반복문을 수행하지 않아도 되기 때문에 시간 복잡도는 상수 시간이다.