Minimum Non-Zero Product of the Array Elements

Minimum Non-Zero Product of the Array Elements - Problem

You are given a positive integer p. Consider an array nums (1-indexed) that consists of the integers in the inclusive range [1, 2^p - 1] in their binary representations. You are allowed to do the following operation any number of times:

Choose two elements x and y from nums.
Choose a bit in x and swap it with its corresponding bit in y. Corresponding bit refers to the bit that is in the same position in the other integer.

For example, if x = 1101 and y = 0011, after swapping the 2nd bit from the right, we have x = 1111 and y = 0001.

Find the minimum non-zero product of nums after performing the above operation any number of times. Return this product modulo 10^9 + 7.

Note: The answer should be the minimum product before the modulo operation is done.

Input & Output

Example 1 — Basic Case

$ Input: p = 1

› Output: 1

💡 Note: Array is [1], so the product is 1

Example 2 — Small Array

$ Input: p = 2

› Output: 6

💡 Note: Array is [1,2,3]. Optimal: swap to get [1,2,3] or [3,2,1]. Product = 1×2×3 = 6

Example 3 — Larger Case

$ Input: p = 3

› Output: 1512

💡 Note: Array is [1,2,3,4,5,6,7]. After optimal swaps: many 1s, many 6s, one 7. Product = 6³ × 7 = 1512

Constraints

1 ≤ p ≤ 60

Visualization

Tap to expand

Understanding the Visualization

Input

Integer p defines range [1, 2^p-1]

Bit Swaps

Rearrange bits to minimize product

Output

Minimum product modulo 10^9+7

Key Takeaway

🎯 Key Insight: Minimize product by creating many 1s through optimal bit distribution

Asked in

G Google 25 f Facebook 18

The key insight is that through bit swapping, we can create an optimal configuration with many 1s and many (2^p-2)s to minimize the product. Best approach uses mathematical formula: (2^p-2)^(2^(p-1)-1) × (2^p-1) with fast exponentiation. Time: O(log p), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Greedy Approach	O(log p)	O(1)	Use mathematical insight to directly calculate minimum product
Brute Force Simulation	O(2^(2^p))	O(2^p)	Generate all numbers, try all possible bit swaps, find minimum product

Mathematical Greedy Approach — Algorithm Steps

Recognize that optimal configuration has many 1s
Remaining numbers should be (2^p-2)
Keep exactly one (2^p-1) to avoid zero product
Use fast exponentiation for large powers

Visualization

Tap to expand

Step-by-Step Walkthrough

Analyze Pattern

Identify optimal configuration

Calculate Formula

Use mathematical formula

Fast Power

Compute result efficiently

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long fastPower(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp = exp >> 1;
        base = (base * base) % mod;
    }
    return result;
}

int solution(int p) {
    long long MOD = 1000000007LL;
    
    if (p == 1) {
        return 1;
    }
    
    long long maxNum = (1LL << p) - 1;
    long long secondMax = maxNum - 1;
    long long count = (1LL << (p - 1)) - 1;
    
    long long powerResult = fastPower(secondMax, count, MOD);
    long long finalResult = (powerResult * maxNum) % MOD;
    
    return (int) finalResult;
}

int main() {
    int p;
    scanf("%d", &p);
    printf("%d\n", solution(p));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log p)

Fast exponentiation takes logarithmic time in the exponent

⚡ Linearithmic

Space Complexity

O(1)

Only uses constant extra space for calculations

✓ Linear Space

23.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler