patterncppMinor
Finding the 'Minimum' AND of all the possible subsets of a set
Viewed 0 times
theallminimumsubsetspossiblefindingandset
Problem
The subset size should be greater than or equal to 2.
How can I speed up this code?
How can I speed up this code?
#include
#include
#include
#include
#include
#include
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 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;
}Solution
There are a few points I'd make about this code.
-
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.
-
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
-
Some of your variable names would benefit from better names.
-
Your code will overflow arithmetic limits on most hardware. In particular:
...attempts to store 2100000 into a
Your only real choices here are to use some type that can store numbers up to 2100000, 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
-
The code above also overflows the end of the array. You've defined the array
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 `
-
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.
-
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.
-
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.-
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).-
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 2100000 into a
long long. On most typical hardware, long long is limited to 263-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 2100000, 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 264-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).-
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 `
-
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.
Code Snippets
power[0]=1;
for(int i=1;i<=100000;i++)
{
power[i]=power[i-1]*2;long long int power[100000];static const int size = 100000;
long long int power[size];
// ...
for (int i=0; i<size; i++)
// write value to power[i]Context
StackExchange Code Review Q#54913, answer score: 3
Revisions (0)
No revisions yet.