minNZproduct.txt

1969. Minimum Non-Zero Product of the Array Elements

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. 
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 109 + 7.

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

class Solution {
public:
    long long modulo = 1000000007;
    
    int power(long long x, long long times){
        if(times==0){
            return 1;
        }
        long long temp = power(x,times/2);
        temp = (temp * temp) % modulo;
        if(times%2){
            temp = (temp * (x % modulo)) % modulo;
        }
        return temp % modulo;
    }

    int minNonZeroProduct(int p) {
        
        long long x = (1ll << p) -1;
        return  x% modulo  * power(x-1, x/2) % modulo;  
    }
};