what is the maximum input value for greedy?

Question

The maximum input value that the "official" reply will calculate is 21474834 which gives an answer of 85899339; which is correct. However if 21474835, or anything higher, is input, the answer is 0.

There was no mention of a maximum input in the problem set so am I missing something that is related to floats, ints, stacks, heaps, or ?????????

thanks

Answer 1

Well, to answer this question you should consider a couple of things

1. The Way You Are Storing the User Input
2. The Way You Are Calculating the Number of Coins

---

First: The Way You Are Storing the User Input

If you're like me, then you probably used GetFloat from the cs50 library which returns a value of type float. A variable of type float is typically 32 bits long. These 32 bits are divided, according to the IEEE 754-1985 standard, into

1. a single bit for the sign
2. 8 bits for the exponent
3. 23 bits for the fraction

The maximum value that can be represented with a float according to this Wikipedia article is ~= 3.4 x 10^38.

---

Second: The Way You Are Calculating the Number of Coins

Again, if you're like me, then you've converted the user input into cents and used ints instead for the sake of precision. Now the maximum value that can be represented with a float as demonstrated above is way beyond the capacity of an int which is also typically 32 bits long.

Since we're dealing with non-negative values, the maximum value that can be stored in an unsigned int is 2^32 - 1 = 4294967295.

If presumably the user entered 3.4 * 10^38 (regardless of the fact of how much he/she paid at the first place to have this amount of change left :D), and if my calculator works correctly, this number would wrap around and become 2268481615 which would lead to calculation errors.

In fact, this is not the first number that would cause these calculation errors. More generally, any value that is when multiplied by 100 and rounded to the nearest int would result in an int value > 4294967295 would cause these calculation errors.

In your case, the first value is 21474835. Recall that you're using a regular signed int and the maximum value that can be stored in a signed int is 2147483647 (i.e., 2^31 - 1)

Answer 2

it should be equal to MAXINT which has 10 digits and not 8. The reason 2 digits are missing, could be this code: sumint = round(sum * 100.0); which makes 8-digit int into a 10-digit int and causes int overflow

https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-a-int32