Wrong answer on HackerEarth

Question

Problem Link:: http://www.hackerearth.com/the-big-bang-challenge/algorithm/subset-and-4/

The problem is that you are given a number Z and some n integers. You have to find whether there is a subset of n integers AND (the bitwise operator) Z gives zero, if it does then print "Yes" else print "No".

I know a simple approach would be just to AND all the input n numbers and Z and see if it gives zero. But I couldn't realize this when I first saw the question. And I actually felt very dumb for it.

This is my code that I first wrote when I read the question::

#include <stdio.h>

int main()
{
    int t;
    int n;
    long int z;
    int i,j,x;
    long int a[1000];
    int b[30];
    int count,count2;
    int flag;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%ld %d",&z,&n);
        count=0;
        for(i=0;i<n;i++)
            scanf("%ld",&a[i]);

        for(i=0;i<30;i++)
            b[i]=-1;
        j=0;
        for(i=0;i<25;i++)
        {
            if(z&1==1)
            {
                b[j++]=i;
                count++;
            }
            z=z>>1;
        }

        flag=0;
        count2=0;
        for(i=0;i<n;i++)
        {

            for(j=0;j<count;j++)
            {
                x=a[i];
                if(b[j]!=-1)
                {
                    x=x>>b[j];
                //    printf("New x=%d\nx&1=%d\n",x,x&1);
                    x==x&1;
                    if(x==0)
                    {
                        count2++;
                        b[j]=-1;
                    }
                  //  printf("Count2=%d and Count1=%d\n",count2,count);

                }

            }
            if(count2>=count)
                {
                    flag=1;
                    break;
                }

        }
        if(flag==0)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}

What my code actually intends to do??

In my code I check the binary representation of the integer Z and count the number of 1s occurring in the number and record the position of 1s in a separate array b[30]. And I store all the n integers in the array a[1000] and check all the integers if any of them have a 0 at the positions that I stored in b[30] and if any of them does then I mark that b[30] position as marked, so that I do not check for that bit position again in the numbers ahead in the a[1000]. If I find a zero for all the positions that I stored in b[30] then I print yes, else I print No.

I know this is a very confusing and a bad algorithm compared to what I should have done. But, please help guys. My code gives wrong answer when I submit it.

For example:: Z=5, then binary of Z will be 1001, i.e, 1 at 0th position and 3rd position. So, in the array b[30], I store the positions in Z where the bit is 1. Like here, I store 0 at b[0] (for first significant bit in Z) and then store 3 at b[1] (for the next significant bit) and I do this for 20 bits (as per my need) and if any bit is 1, then I store its position in b[j++].

Then, I start taking all the elements that I stored in a[1000] one by one and store them in x, then take 1 position from b[30] array, that I previously processed, right shift x by that much positions and check if the right most bit is 1. For example, my a[1000] array has 2 elements, 3 and 1. 3 is 0011, I store 3 in x, take b[0] and then perform x>>b[0], which is the same in this case 0011 (since b[0] is 0). Then I check the right most bit by performing x&1, which returns 1, hence that bit is not zero, so I move ahead to b[1] which is 3, then I perform x>>b[1], which gives 0000, then I check x&1 which gives me zero. So, now I know that I have a number in the array that has the 3rd bit zero, so I mark b[1] as -1, so that I do not check it again for the next integer in a[1000]. Then I take 1 which is the second element of a[1000], and then do the same steps as above and I find that I do not have an element in a[1000] with 0th bit as zero. So, I do not have elements which have zero bit at the position where Z was 1. So, there AND will never be zero and so I print No.

The problem statement::(As on HackerEarth)

You are given a number Z and a set S with N elements. Your job is to find a sub set of S such that the AND of the given number and this subset is zero. If this sub set is possible print "Yes" otherwise print "No"

Input First line contains number of test case T. Each test case contains two lines , first line contains two numbers Z and N , where Z is given number and N is size of set S . Second line contains N elements of the subset S.

Output For each test case print Yes if the subset is possible else print No .

Constraints: 1<=T<=100 1<=N<=1000 0<=Ai<=Z<=1000000

Sample Input 3 10 2 2 0 10 3 1 1 1 5 3 1 5 3

Sample Output Yes Yes No

My code gives correct answer for the sample input but fails on HackerEarth Submission. Please help guys.. Thanks for any help in advance.. :)

Answer 1

Your idea is also good, but you are over-complicating it a little. Can you think how you can simplify it more (do less things than you describe, but keep the same general line of thinking)? Read on for how.

And I store all the n integers in the array a[1000]

You do not need to store them: you will only use each of them once, so don't bother storing them. Just read and process each one in turn.

and check all the integers if any of them have a 0 at the positions that I stored in b[30] and if any of them does then I mark that b[30] position as marked, so that I do not check for that bit position again

No need to mark or bother about not checking again. How can you do this more easily? Simply decrement each b[i] for each zero you find in a number at position i. Then, you will print yes if b contains only numbers <= 0.

Now, we've eliminated two of the things you wanted to do, while keeping your idea intact. This is good, because if we do less work, we have fewer chances of doing something wrong.

I realize this doesn't answer what is wrong with your code. My point is, by thinking a little bit more about your ideas, you can write better code, that is most likely to work. In this case, you'd get rid of a lot of needless baggage, giving you less opportunity to make mistakes.

As for where exactly your code is wrong, there are quite a few things, but the most important part is this:

    for(i=0;i<n;i++)
    {

        for(j=0;j<count;j++)
        {
            x=a[i]; <= you are setting x for each j. 
                       You probably want this a level up, in the other loop?
            if(b[j]!=-1) <= don't need this the way I described it.
            {
                x=x>>b[j]; <= b[j] has no bearing on how much you shift x by. 
                              You probably meant x = x>>j? 
                              But wait, that's wrong too, because we're in a loop, 
                              so we'll shift by too much! Maybe x = x>>1?
            //    printf("New x=%d\nx&1=%d\n",x,x&1);
                x==x&1; <= this doesn't do anything. Why? 
                           What is the difference between == and =?
                           Do you want to use =, or move this in the if below?
                if(x==0)
                {
                    count2++;
                    b[j]=-1;
                }
              //  printf("Count2=%d and Count1=%d\n",count2,count);

            }
        }
        if(count2>=count)
        {
            flag=1;
            break;
        }
    }

I suggest a programming tutorial, such as this one: http://www.cprogramming.com/tutorial/c-tutorial.html and others on that site to get you started before attempting to solve contest problems.