Minimum Non Zero Product Of The Array Elements - Leetcode Solution

Problem Statement:

Given an integer array nums, find the minimum non-zero product of any permutation of nums.

Since the answer may be large, return it modulo 109 + 7.

Approach:

We need to minimize the product of the array, so we would like to minimize the product of the larger numbers. Also, since the array must be permuted, we can sort the array and try to multiply the elements from the end.

If the array contains 0 or 1, then the minimum non-zero product must be 1. Otherwise, we need to consider the product of the two smallest non-zero numbers. If all numbers are non-zero, then we need to consider the product of the two smallest non-zero numbers, and we need to do this modulo 10^9 + 7.

To get the product of the smaller numbers, we can multiply them together and then divide the result by the largest factor of 2 that divides the product. If the product is odd, then we need to subtract 1 before dividing.

Code:

int MOD = 1000000007;

int minNonZeroProduct(int p) { long long n = (1LL << p) - 1LL; long long x = (n - 1LL) % MOD; long long y = (n / 2LL) % (MOD - 1LL); long long z = (x * y) % (MOD - 1LL); long long ans = 1LL; for(int i = 0; i < p; i++) { ans = (ans * n) % MOD; n--; } return ans * fastPow(2LL, z) % MOD; }

int fastPow(long long a, long long b) { long long res = 1LL; while(b) { if(b & 1LL) res = res * a % MOD; b >>= 1LL; a = a * a % MOD; } return res; }

Time Complexity:

The time complexity of the above code is O(log n), where n is the largest number in the array.

Space Complexity:

The space complexity of the above code is O(1).

Example:

Input: p = 3 Output: 12

Explanation: The array nums = [1,2,3] permuted becomes [2,3,1] with a product of 2 * 3 * 1 = 6, which is not optimal, as the array permuted becomes [3,1,2] with a product of 3 * 1 * 2 = 6, which is optimal.

Input: p = 1 Output: 1

Explanation: There is only one element in the array, so the minimum non-zero product must be 1.

1