title: Wrong answer on HackerEarth
body: <p>Problem Link:: <a href="http://www.hackerearth.com/the-big-bang-challenge/algorithm/subset-and-4/" rel="nofollow">http://www.hackerearth.com/the-big-bang-challenge/algorithm/subset-and-4/</a></p>
  
  <p>The problem is that you are given a number <code>Z</code> and some <code>n</code> 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".</p>
  
  <p>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. </p>
  
  <p>This is my code that I first wrote when I read the question::</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  
  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",&amp;t);
      while(t--)
      {
          scanf("%ld %d",&amp;z,&amp;n);
          count=0;
          for(i=0;i&lt;n;i++)
              scanf("%ld",&amp;a[i]);
  
          for(i=0;i&lt;30;i++)
              b[i]=-1;
          j=0;
          for(i=0;i&lt;25;i++)
          {
              if(z&amp;1==1)
              {
                  b[j++]=i;
                  count++;
              }
              z=z&gt;&gt;1;
          }
  
          flag=0;
          count2=0;
          for(i=0;i&lt;n;i++)
          {
  
              for(j=0;j&lt;count;j++)
              {
                  x=a[i];
                  if(b[j]!=-1)
                  {
                      x=x&gt;&gt;b[j];
                  //    printf("New x=%d\nx&amp;1=%d\n",x,x&amp;1);
                      x==x&amp;1;
                      if(x==0)
                      {
                          count2++;
                          b[j]=-1;
                      }
                    //  printf("Count2=%d and Count1=%d\n",count2,count);
  
                  }
  
              }
              if(count2&gt;=count)
                  {
                      flag=1;
                      break;
                  }
  
          }
          if(flag==0)
              printf("No\n");
          else
              printf("Yes\n");
      }
      return 0;
  }
  </code></pre>
  
  <p><strong>What my code actually intends to do??</strong></p>
  
  <p>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 <code>b[30]</code>. And I store all the <code>n</code> integers in the array <code>a[1000]</code> and check all the integers if any of them have a <code>0</code> at the positions that I stored in <code>b[30]</code> 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.</p>
  
  <p>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.</p>
  
  <p>For example:: Z=5, then binary of Z will be <code>1001</code>, i.e, <code>1</code> 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 <code>0</code> at <code>b[0]</code> (for first significant bit in Z) and then store <code>3</code> 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 <code>b[j++]</code>.</p>
  
  <p>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 <code>b[30]</code> 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 <code>x&amp;1</code>, 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 <code>0000</code>, then I check x&amp;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 <code>1</code> 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 <code>No</code>.</p>
  
  <p>The problem statement::(As on HackerEarth)</p>
  
  <blockquote>
    <p>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"</p>
    
    <p>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.</p>
    
    <p>Output For each test case print Yes if the subset is possible else
    print No .</p>
    
    <p>Constraints: 1&lt;=T&lt;=100 1&lt;=N&lt;=1000 0&lt;=Ai&lt;=Z&lt;=1000000</p>
  </blockquote>
  
  <p>Sample Input
  3
  10 2
  2 0
  10 3
  1 1 1
  5 3
  1 5 3</p>
  
  <p>Sample Output
  Yes
  Yes
  No</p>
  
  <p>My code gives correct answer for the sample input but fails on HackerEarth Submission.
  Please help guys..
  Thanks for any help in advance.. :)    </p>