Range of int: Bytelandian Gold Coins Problem

general
, ,
1

I don’t know what’s the issue here: My program is working fine when I use unsigned long int but it gives WA in case of long int or int.

As far as I know range of int on 32 bit machine is 10^9… so my program should work fine using int(since range of n is <= 10^9) but it does not.

my code is


#include<stdio.h>
int amt[100000] = {0};
unsigned long int max(unsigned long int n)
{
    int val = 0;
    if(n <12)
        return n;
    else if (n<100000)
    {
        if(amt[n]!=0)
            return amt[n];
        else
        {
            val = max(n/2)+max(n/3)+max(n/4);
           amt[n] = val;
           return val;
        }
    }
    else
    {
        val = max(n/2)+max(n/3)+max(n/4);
        return (n>val?n:val);
    }
}
int main()
{
    unsigned long int n;
    while(scanf("%lu",&n) != EOF)
    {
        printf("%lu\n", max(n));
    }
    return 0;
}

Kindly Help.

1 Like
2

The answer to the input 109 is 4243218150.

This number needs 32 bits to represent the magnitude alone. So, in sign-magnitude form, it needs at least 33 bits.

The int datatype is signed 32-bit representation. It uses only 31 bits to represent magnitude. Your program would have passed, if you used unsigned int.

Now, it may amuse you that long and int are usually 32-bit long here. To get 64-bit numbers, you need to use long long (for signed) and unsigned long long (for unsigned).

the reasoon why your program got accepted is not because you used long. But, it is because you used unsigned.

2 Likes
3

The inputs are all well within range. But there is no guarantee in the question, that the output will also fit in signed integer.

4

Thanks tijoforyou.
I just want to ask one more question, as you pointed out that long and int are only 32-bit long. So what is the need of long?

5

You might be aware that there is a type short as well.

So, we have short (same as short int), int, long (same as long int) and long long. The only guarantee (and restriction to compiler writers) is that sizeof(short) <= sizeof(int) <= sizeof(long) <= sizeof(long long).

So, in some machines, long might have larger size than int. (E.g.: Turbo C has 16-bit “int” and 32-bit “long” datatypes.)

So, the data types do exist. In the gcc versions used here, sizeof(int) is same as sizeof(long).