Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python을 사용하여 합이 홀수인 하위 배열의 수를 찾는 프로그램

<시간/>

배열 arr이 있다고 가정합니다. 합이 홀수인 부분배열의 수를 찾아야 합니다. 답이 너무 크면 10^9+7 모듈로 결과를 반환합니다.

따라서 입력이 arr =[8,3,7]과 같으면 모든 하위 배열이 [[8],[3],[7],[8,3],[3, 7],[8,3,7]] 이제 합 값은 [8,3,7,11,10,18]이므로 세 개의 홀수 합 값 [3,7,11]이 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • freq :=두 개의 요소 1과 0을 가진 목록

  • 답변 :=0

  • 접두사 :=0

  • arr의 각 x에 대해 수행

    • 접두사 :=접두사 + x

    • ans :=ans + freq[1 XOR 접두어 AND 1]

    • freq[접두사 AND 1] :=freq[접두사 AND 1] + 1

  • 모드로 반환(10^9+7)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

def solve(arr):
   freq = [1, 0]
   ans = prefix = 0
   for x in arr:
      prefix += x
      ans += freq[1 ^ prefix&1]
      freq[prefix &s; 1] += 1
   return ans % (10**9+7)
arr = [8,3,7]
print(solve(arr))

입력

[8,3,7]

출력

3