Finding the 'Minimum' AND of all the possible subsets of a set

Question

The subset size should be greater than or equal to 2.

How can I speed up this code?

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<malloc.h>
#include <iostream>
#include <vector>
long long int set[100000];
long long int counter, j;
long long int ans,min,count;
bool ha;
long long int pow_set_size;
long long int power[100000];
void printPowerSet(long long int set_size)
{
 pow_set_size =power[set_size];
 count=4;
 for(counter = 3; counter < pow_set_size; counter++)
 {
 ha=0;
 if(counter!=count)
 { 
 for(j = 0; j < set_size; j++)
 {
 if(counter & (1<<j))
 {
 if(!ha)
 {
 ans=set[j];
 ha=1;
 }
 else
 { 
 ans=((ans) & (set[j]));
 }
 }
 }
 // printf("%lld\n",ans);
 if(counter==3)
 { 
 min=ans;
 }
 else if(min>ans)
 {
 min=ans;
 }
 } 
 else
 {
 count=count*2;
 }
 }
 printf("%lld\n",min);
}
void pre()
 {
 power[0]=1;
 for(int i=1;i<=100000;i++)
 {
 power[i]=power[i-1]*2;
 }
}
int main()
 {
 long long int test;
 long long int len;
 long long int a;
 scanf("%lld",&test);
 pre();
 while(test--)
 {
 scanf("%lld",&len);
 for(int i=0;i<len;i++)
 {
 scanf("%lld",&set[i]);
 }
 printPowerSet(len);
 }
 return 0;
}

• Jamal: This is very C-like, with the exception of <iostream> and <vector>. Are you still trying to implement it in C++ specifically?

Answer 1

There are a few points I'd make about this code.

1. Choose your language. Right now, you're using a number of C++ headers, so a C compiler can't process your code. Unfortunately, you don't seem to be putting any C++ features to use to make the code more readable, understandable or safe than C code would be.

2. If you are going to write C++, one starting point is to avoid using built-in array types (as a rule) and printf/scan (nearly always). Unless you have some very specific reason to do otherwise, you're usually better off using std::vector instead of an array, and iostreams instead of printf/scanf.

3. Some of your variable names would benefit from better names. ha and ans were the two that I found particularly difficult to understand (to the point that I'm still not entirely sure what they mean).

4. Your code will overflow arithmetic limits on most hardware. In particular:

   power[0]=1;
   for(int i=1;i<=100000;i++)
   {
    power[i]=power[i-1]*2;
   

   ...attempts to store 2¹⁰⁰⁰⁰⁰ into a long long. On most typical hardware, long long is limited to 2⁶³-1. Although hardware may (probably will) someday expand from its current 64-bit word size to something larger, and long long may expand when it does so, this won't work on most current implementations, and I don't think we can expect to see implementations where it will work any time soon either.

   Your only real choices here are to use some type that can store numbers up to 2¹⁰⁰⁰⁰⁰, or else do things some other way so you don't need to store such large numbers. Oh, the final possibility would be to use unsigned long long, and live with the fact that you're storing the value modulo 2⁶⁴-1. For some purposes this works quite nicely (but I'm not sure what you're really using this for, so I'm not sure whether it's adequate for your purposes or not).

5. The code above also overflows the end of the array. You've defined the array power as:

   long long int power[100000];
   

   This means the valid subscripts into this array run from 0 through 99999. Unfortunately, your code loops through 100000, so it tries to write to an element one beyond the end of the array, which gives undefined behavior.

   In C and C++, you typically use < for the comparison in a loop like this, so you'd use something like:

   static const int size = 100000;
   long long int power[size];
   // ...
   for (int i=0; i<size; i++)
    // write value to power[i]
   

6. Indentation. Sometimes indentation gets messed up when you paste here (especially if you have a mixture of tabs and spaces to indent lines), but you definitely want indentation to be more consistent than the code the way I'm seeing it above.

• murdocc_007: Thanks for the comments.I've made your recommended changes. Still getting TLE. Any points on improving performance?