Minimum Non-Zero Product of the Array Elements — LeetCode 1969 Python Solution
MediumGreedyRecursionMath
- Problem
- #1969
- Pattern
- Greedy
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given a positive integer p. Consider an array nums (1-indexed) that consists of the integers in the inclusive range [1, 2p - 1] in their binary representations.
Example
- Input
- p = 1
- Output
- 1
- Explanation
- nums = [1].
Python solution
Python
class Solution:
def minNonZeroProduct(self, p: int) -> int:
mod = 10**9 + 7
return (2**p - 1) * pow(2**p - 2, 2 ** (p - 1) - 1, mod) % modComplexity
| Measure | Complexity |
|---|---|
| Time | O(p) |
| Space | O(1) auxiliary |
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 1969. Minimum Non-Zero Product of the Array Elements is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1969. Minimum Non-Zero Product of the Array Elements?
- LeetCode 1969. Minimum Non-Zero Product of the Array Elements is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1969. Minimum Non-Zero Product of the Array Elements?
- The Python solution on this page runs in O(p).
- What is the space complexity of LeetCode 1969. Minimum Non-Zero Product of the Array Elements?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1969. Minimum Non-Zero Product of the Array Elements cover?
- LeetCode 1969. Minimum Non-Zero Product of the Array Elements is tagged Greedy, Recursion and Math on LeetCode.