We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Red John is Back
  5. Discussions

Red John is Back

  • AbdelrhmanAdawy
     + 0 comments

    the idea in this problem is to divide the bricks into horizontal blocks and evaluate the compensation using nCr, then break the blocks down into 4 vertical bricks until reach to no horizontal block remaining, and count the combination of each loop.

    To optimize the speed of nCr, we could just simplify the rule into two for loops, one for the numerator and the other for the detonatorinstead of using 3 factorials.

    Also, to optimize the prime number counting, we could store the prime numbers and divide on them instead of doing a loop for all possible combinations each time.

    here is my code using C language 

    int nCr(int n , int r)
{
    if(r>n || r<0)
    {
        return -1;
    }
    else if (r == 0 || r == n) {
        return 1;
    }
    else if (r == 1) {
        return n;
    }
    else {
        if(r < n/2)
        {
            r = (n-r);
        }
        
        unsigned long long int Numerator = 1, denominator = 1 , result = 0;
        int i = 0;
    
        for(i = r+1 ; i <= n ; i++)
        {
            Numerator *= i;
        }
        
        for(i = 2 ; i <= (n-r) ; i++)
        {
            denominator *= i;
        }
        printf("Numerator = %ld , denominator = %ld\n" ,Numerator , denominator);
        result = Numerator/denominator;
        
        return (int)result;
    }
}

int prime_counter(int n)
{
    if(n<2)
    {
        return 0;
    }
    else if (n<3) {
        return 1;
    }
    else if (n<5) {
    return 2;
    }
    else if (n<7) {
        return 3;
    }
    else if (n<11) {
        return 4;
    }
   else 
   {
    int count = 0 , i =0 , j = 0;


    int* stroed_prime_numbers = calloc(n , sizeof(int));
    stroed_prime_numbers[count++] = 2;
    stroed_prime_numbers[count++] = 3;
    stroed_prime_numbers[count++] = 5;
    stroed_prime_numbers[count++] = 7;

    for (i = 11; i<=n ; i++) 
    {
        for(j = 0 ; j < count ; j++)
        {
            if(i % stroed_prime_numbers[j] == 0 )
            {
                break;
            }
        }
        if( j >= count )
        {
            stroed_prime_numbers[count++] = i;
        }
    }

    return count;
   }
}

int redJohn(int n) {
    int num_Horizontal_block_bricks = n/4 , rem_vertical_bricks = 0 , prime_count = 0 , num_of_arrangements = 1 , i=0 , ncr = 0;
    
    for(i = num_Horizontal_block_bricks ; i > 0 ; i--)
    {
        rem_vertical_bricks = n - (4*i);
        ncr = nCr( i + rem_vertical_bricks , i );   
        num_of_arrangements += ncr;
    }

    prime_count = prime_counter(num_of_arrangements);
    
    return prime_count;
}