Subset Sum program in C

Question

i was on to writing the program of subset sum problem in c. The program run just fine when number of element in the array <=30 , if number of element in the array are > 30 , program doesn't work correctly and gives the exection "An unhandled exception of type 'System.DivideByZeroException' occurred"

Source Code:

 #include<stdio.h>
  #include<math.h>
 int power(int a,int b)
{
    int i=2;
    int base=2;
    if(b==0)
        return 1;
    if(b==1)
        return a;
    else
    while(i<=b)
    {
        a=a*base;
        i++;
    } 
    return a;
}

int main()
{    
    int n,p,q,s,sum;
    n=30;       // no. of element in the array. 
    p=0;
    q=0;
    sum=0;

    int aa[30]={3,2,5,1,9,4,5,1,33,23,87,132,74,63,19,2,32,75,17,32,93,34,4,54,12,95,34,82,75,83};

    s=power(2,n);     // no. of subsets in the set

    while(p<=s)
    {        
         while(q<n)
         {
             if(power(2,q)<=(p%power(2,q+1)) && (p%power(2,q+1))<=(power(2,q+1)-1) )
                 sum=sum+aa[(n-1)-q];
             q++;
         }

          if(sum==16)
         {
             printf("Found the SUM at row %d",p);

         }

          sum=0;
         p++;
         q=0;
    }
         printf("Not Found");

}

enter image description here

So this is C code but you get a C# exception? Good trick. Also why write a general power method just to do 1 << n? — user555045
– user555045, Commented Nov 6, 2014 at 16:27

Bathsheba · Accepted Answer · 2014-11-06 16:58:30Z

4

You get a division by zero as your int type is overflowing. (power(2, 32) is probably being evaluated as 0 but you should view this as a coindicence since signed overflow is undefined behaviour in C).

In C you can use uint64_t which is a 64 bit unsigned integer type. That's been there since (and including) C99. Note that unsigned overflow is defined in C to be reduced modulo power of 2

This will give you good results up to power(2, 63).

edited Nov 6, 2014 at 16:58

answered Nov 6, 2014 at 16:33

Bathsheba

235k35 gold badges376 silver badges504 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Bathsheba Over a year ago

@DarkDust: (drinking coffee). Of course you're right. We'll publish jointly.

Paul R · Accepted Answer · 2014-11-06 16:37:09Z

1

With 32 bit signed ints you can can only represent values up to 2^31 - 1, hence n must be <= 30. Use 64 bits ints (preferably unsigned) for larger values of n, e.g.

int n = 60;
uint64_t s = 1ULL << n;    // s = pow(2, n) = pow(2, 60)

edited Nov 6, 2014 at 16:37

answered Nov 6, 2014 at 16:31

Paul R

214k38 gold badges402 silver badges579 bronze badges

Comments

Akshay Rao · Accepted Answer · 2014-11-06 16:32:42Z

0

s is a signed int and you're uncomfortably close to overflowing it with s = power (2, n) when n is greater than 31.

answered Nov 6, 2014 at 16:32

Akshay Rao

3421 silver badge7 bronze badges

Collectives™ on Stack Overflow

Subset Sum program in C

3 Answers 3

1 Comment

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Related