Problem Statement: Given an array arr of n integers, count the number of non-empty subsequences of the given array such that their product of maximum element and minimum element is zero. Since this number can be huge, compute it modulo 10 ^ 9 + 7 A subsequence of an array is defined as the sequence obtained by deleting several elements from the array (possible none) without changing the order of the remaining elements.
Example Given n = 3, arr = [1, 0, – 2].
There are 7 subsequences of arr that are-
[1], minimum = 1, maximum =1 , min * max = 1 .
[1,0] minimum = 0, maximum=1, min * max=0
[ 1,0, – 2], minimum = – 2, maximum =1, min* max = -2.
[0], minimum = 0, maximum =0, min * max=0
[0,-2],minimum=-2,maximum=0, min* max=0,
[1, -2] minimum=-2, maximum=1,min* max=-2
[- 2] minimum =-2 maximum = – 2 , min* max = 4.
There are 3 subsequences whose minimum * maximum = 0 that are
[1, 0], [0], [0, – 2] . Hence the answer is 3.
I tried to come up with a solution, by counting the number of zeroes, positive numbers and negative numbers and then adding possible subsequences(2^n, per count) to an empty variable.
My answer is way off though, it's 10 when the expected answer is 3. Can someone please point out my mistake?
#include<bits/stdc++.h>
using namespace std;
#define int long long
int zeroSubs(vector<int> arr){
int x = 0, y = 0, z = 0, ans = 0;
for(int i = 0; i < arr.size(); i++){
if(arr[i] == 0) z++;
else if(arr[i] < 0) x++;
else y++;
}
ans += ((int)pow(2, z))*((int)pow(2, x));
ans += ((int)pow(2, y))*((int)pow(2, z));
ans += ((int)pow(2, z));
return ans;
}
int32_t main()
{
//directly passed the sample test case as an array
cout<<zeroSubs({1, 0, -2});
return 0;
}
ans += ((1<<z)-1)*((1<<x)-1);
ans += ((1<<y)-1)*((1<<z)-1);
ans += ((1<<z)-1);
Made this slight change in the logic, thanks a lot to everyone for the valuable feedback. It works now.