Recursion if condition

Question

The following is the implementation of the problem from spoj: - http://www.spoj.com/problems/COINS/

#include <stdio.h> #define ll long long ll arr[100000]; ll max(ll n) { if(n < 49999)// Doubt { if(!arr[n]) return arr[n] = max(n/2) + max(n/3) + max(n/4); else return arr[n]; } else return max(n/2) + max(n/4) + max(n/3); } int main() { ll n, c = 0, i; for(i = 0; i < 12; i++) // Also why 12 when the input can be <12 { arr[i] = i; } while(scanf("%lld", &n) != EOF) { printf("%lld\n", max(n)); } return 0; } 

Why does the if condition contain n <49999?

Answer 1

without considering every opportunity other than the first 20+ and the maximum and minimum values:

My expectation

The first 12 entries in arr [] are precomputed to reduce the recursion depth, but the dollar value does not match the calculated value for these first 12 entries.

for coin values ​​<= 49999, check if the value has already been calculated, if then you do not split the coin into values ​​/ 2/3/4 and repeat each of these resulting values.

This limit value (49999) can be increased to 100000, since this is the available size of the arr [] array.

presetting and saving to the arr [] array will help reduce execution time and recursion depth.

using an array so that any previously calculated values ​​(in published code up to 49999) can be immediately returned by the max() function without further recursion.

I would modify the code a bit for better documentation and reliability and faster execution as follows:

 #include <stdio.h> #include <stdint.h> #define MAX_ARRAY_LEN (100000) uint32_t arr[ MAX_ARRAY_LEN ] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; uint32_t max(uint32_t n) { if(n < MAX_ARRAY_LEN) { // value of 'n' within the range of the learning array arr[] if(!arr[n] && n) { // then learning array arr[] not yet set return arr[n] = max(n/2) + max(n/3) + max(n/4); } else { // else learning array arr[] already set for 'this' value of 'n' return arr[n]; } } else { // value of 'n' is greater than the learning array arr[] return max(n/2) + max(n/4) + max(n/3); } } // end function: max int main( void ) { uint32_t n; int status; while( (status = scanf("%u", &n)) == 1 && EOF != status) { if( 1000000000 >= n) { printf("%u\n", max(n) ); } else { printf(" invalid value entered, must be in the range 0...1 000 000 000\n"); } // end if } // end while return 0; } // end function: main 

Answer 2

As far as I understand,

The person who writes the code somehow found that (manually) if the coin is less than 12, then the result will be by itself. so he uses 12.
(check input coin explanation = 2)

And about the recursion function

since we know that we cannot declare an array of size 1,000,000,000 so that it tries to use a different value (49999 here), in what size can it create an array and later take the result for a coin in the array, like arr [12] = 13 (where 12 is a coin, and 13 is the result), so that he can get the result without generating for the value, using this array with arr [12] (only) for coin 12.

I hope you understand.