LeetCode #1969 Minimum Non-Zero Product of the Array Elements

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #1969 Minimum Non-Zero Product of the Array Elements

문제 풀이

길이 n의 비트로 구성할 수 있는 0을 제외한 수들에 대해 비트 전환을 수행하고서 0이 아닌 원소들의 곱의 최솟값을 구해야 한다. 주간 챌린지로 출제된 문제인데 처음에는 뇌정지가 왔다가 풀이를 보고 너무나 간단한 문제라 허탈했다. 익히 우리는 합이 일정한 경우 두 수의 차가 최대인 수의 곱이 최솟값이 됨을 알 수 있다. 그리고 n개 비트로 생성할 수 있는 수는 $2^n$개 이고 0이 제외되었으므로 $2^n - 1$개인데 최댓값은 1로밖에 구성되지 않아 비트 전환을 할 수 없다. 따라서 나머지 원소는 $2^n - 2$개로 짝수가 되어 한 쌍씩 짝지을 수 있다. 따라서 한 쪽을 1로 두고 다른 한 쪽을 1의 자리만 0인 수로 서로 비트를 교환할 수 있어 $2^n-2$의 $2^{n-1} - 1$제곱과 $2^n-1$을 곱하면 정답에 활용할 수 있다.

• n개 비트로 생성할 수 있는 최댓값은 $2^n - 1$이다.
• 나머지 원소들이 비트 교환했을 때의 최댓값은 $2^n-2$이다.
• 최댓값을 제외한 나머지 원소들의 절반은 1로 변환되므로 $(2^n-2)//2$가 곱해질 수의 개수다.
• 큰 자리의 pow 연산은 자리 수가 커서 속도가 느리다. 문제에서 특정 수로 나누기를 요구했으므로 제곱 연산에 나누는 과정을 넣는다.
• 마지막으로 도출된 값에도 전체 생성 숫자의 최댓값을 곱하고 나머지 연산하여 리턴

python 코드

class Solution:
    def minNonZeroProduct(self, p: int) -> int:
        MOD = 10 ** 9 + 7
        def fastPow(base, power):
            if power == 0:
                return 1
            res = fastPow(base, power // 2)
            res = (res * res) % MOD
            if poser % 2 == 1:
                res *= base
            return res
        biggest = 2 ** p - 1
        val = biggest - 1
        time = val // 2
        result = fastPow(val, time)
        return (result * biggest) % MOD