Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Project Euler 104

wavicle Feb 13th, 2016 (edited) 103 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. //Project Euler problem 104, 100% brute force
  2. //finds the index of the first Fibonacci whose first and last nine digits are 1-9 pandigital but not necessarily in order
  3.  
  4. #include <stdio.h>
  5.  
  6. int main()
  7. {   int fib_index=2, solutions=0;
  8.    
  9.     int top_term[70000]={0};
  10.     int bottom_term[70000]={0};
  11.    
  12.     top_term[69999] = 1;    //fibonacci_2
  13.     bottom_term[69999] = 1; //fibonacci_1
  14.    
  15.     int marker=69998; //fib beginning marker
  16.    
  17.     while(solutions == 0)
  18.     {   for(int temp, a=69999; a >= marker; a--) //generate fibonacci (for loop)
  19.         {   temp = top_term[a];
  20.             top_term[a] += bottom_term[a];
  21.             bottom_term[a] = temp;
  22.            
  23.             if(top_term[a] > 9) //(if sum > 9, carry the one)
  24.             {   top_term[a] %= 10;
  25.                 bottom_term[a-1]++;
  26.             }
  27.         }
  28.        
  29.         fib_index++;
  30.         if(top_term[marker] != 0) marker--;
  31.        
  32.         //check right fibonacci end
  33.         int pan[10]={0}, approve_left=0, approve_right=0;
  34.        
  35.         for(int temp, a=69991; a <= 69999; a++) //give pan[] right digits
  36.         {   temp = top_term[a];
  37.             pan[temp]++;
  38.         }
  39.        
  40.         if(pan[0] != 0) continue;
  41.        
  42.         for(int a=1; a <= 9; a++) //check right if pandigital
  43.         {   if(pan[a] == 1)
  44.             {   approve_right++;
  45.             }
  46.         }
  47.        
  48.         //check left fibonacci end
  49.         if(approve_right != 9 || marker+1 > 69981) continue;
  50.        
  51.         for(int a=0; a <= 9; a++) //reset pan[]
  52.         {   pan[a] = 0;
  53.         }
  54.        
  55.         for(int a=marker+1, temp; a <= marker+9; a++) //give pan[] left digits
  56.         {   temp = top_term[a];
  57.             pan[temp]++;
  58.         }
  59.        
  60.         if(pan[0] != 0) continue;
  61.        
  62.         for(int a=1; a <= 9; a++) //check left if pandigital
  63.         {   if(pan[a] == 1)
  64.             {   approve_left++;
  65.             }
  66.         }
  67.        
  68.         if(approve_left == 9 && approve_right == 9)
  69.         {   solutions++;
  70.         }
  71.     }
  72.    
  73.     printf("fib_index: %i\n\n", fib_index);
  74.    
  75.     return 0;
  76. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top