Funcia
Lv.1arraymathprefix-sum

합이 홀수인 구간 세기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

정수 배열 nums가 주어집니다. 길이가 1 이상인 연속 구간 nums[l..r](0 ≤ l ≤ r < n) 중에서 원소의 합이 홀수인 구간의 개수를 반환하세요.

구간은 시작과 끝 위치로 구별합니다. 값이 같은 구간이라도 위치가 다르면 다른 구간입니다.

입출력 예

numsresult
[1, 3, 5]4
[2, 4, 6]0
[1, 2, 3, 4, 5, 6, 7]16

입출력 예 설명

예 1 — 구간은 [1], [3], [5], [1, 3], [3, 5], [1, 3, 5]이고 합은 1, 3, 5, 4, 8, 9입니다. 홀수인 구간은 4개입니다.

예 2 — 짝수만 있으므로 어떤 구간의 합도 홀수가 아닙니다.

예 3 — 28개의 구간 중 16개의 합이 홀수입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(nums: int[]) → long

제한 사항

  • 1≤1 \le nums.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le nums[i] ≤109\le 10^9
  • 답은 32비트 정수 범위를 넘을 수 있습니다. 64비트 정수(long)를 사용하세요.

기대 복잡도

시간
O(N)
공간
O(1)

입출력 예

nums기대 출력
[1,3,5]4
[2,4,6]0
[1,2,3,4,5,6,7]16

힌트

힌트

누적 합 P[k] = nums[0] + … + nums[k-1](P[0] = 0)을 생각하면 구간 nums[l..r]의 합은 P[r+1] - P[l]입니다.

두 수의 차가 홀수인 것은 두 수의 홀짝이 다를 때뿐입니다. 그러니 실제 합은 필요 없고, 지금까지 나온 누적 합 중 짝수인 것의 개수와 홀수인 것의 개수만 세면 됩니다. 새 누적 합이 홀수이면 지금까지의 짝수 개수만큼, 짝수이면 홀수 개수만큼 답에 더합니다.

음수의 홀짝을 판별할 때 언어에 따라 x % 2가 -1이 될 수 있으니 주의하세요. x & 1을 쓰거나 x % 2 != 0으로 비교하면 안전합니다.

복잡도 목표

모든 구간의 합을 하나씩 확인하면 O(N2)O(N^2)으로 시간 초과입니다. 누적 합의 홀짝 개수만 세면 O(N)O(N)입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251102 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4010판정만
performance603판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.