-4

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;
}
hecker
  • 9
  • 4
  • 3
    Tip: Forget `pow`. Use `<<` for powers of 2. Stay *well away* from floating point math when doing precise integer math. – tadman Aug 05 '22 at 20:50
  • What should `zeroSubs({0})` return? Can you see why your code returns `6` subsets, given that input? Effectively, your invented formula does not produce the correct answer. `zeroSubs({0,0,0})` returns `24`. – Drew Dormann Aug 05 '22 at 20:53
  • Explain (to us, or to yourself) what you mean by the `ans += ... pow ...` lines. E.g. you have `[1, 0, -2, 0, -2, 0, 1]`. – lorro Aug 05 '22 at 20:54
  • 4
    *Can someone please point out my mistake?* -- Please [debug](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) your code. You wrote the code, you have the test case, you wrote the code with a plan in mind -- the next step is to use the debugger to see where the program diverts from the plan you had. – PaulMcKenzie Aug 05 '22 at 20:54
  • 1
    *there's something wrong with my algorithm* -- Then you shouldn't have written a program that follows something that is broken. You need to make sure that your plan/algorithm is sound before you write a single line of code. Also, `#define int long long` -- do **not** do this. If you want a `long long`, then `int64_t` is the type you should be using, without using that awful and program breaking `#define` you have. That's why you have this: `int32_t main()` -- totally weird to any C++ programmer. – PaulMcKenzie Aug 05 '22 at 20:56
  • 1
    `int32_t main()` is a bad idea. Don't you want the program to be accepted by compilers where `int` is not the same as `int32_t`? – Ted Lyngmo Aug 05 '22 at 21:09

1 Answers1

-1
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.

hecker
  • 9
  • 4