Solution to Problem 24 on Project Euler


The problem:


A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

My solution:

#include <stdio.h>

#define LIMIT 1000000

int fat(int n){
  int fato = 1;
  while (n>1){
    fato = fato * n;
    n = n - 1;
  }
  return fato;
}

int nextDigit (int array[10]){
  int x = 0;
  while (x<20){
    if (array[x]<10)
      return array[x];
    x++;
  }
return 0;
}

int digitPlus(int digit,int array[10]){
  if (digit==9)
    digit=0;
  if (array[digit+1]<10)
    return array[digit+1];
  else if (array[digit+2]<10)
    return array[digit+2];
  else if (array[digit+3]<10)
    return array[digit+3];
  else if (array[digit+4]<10)
    return array[digit+4];
  else if (array[digit+5]<10)
    return array[digit+5];
  else if (array[digit+6]<10)
    return array[digit+6];
  else if (array[digit+7]<10)
    return array[digit+7];
  else if (array[digit+8]<10)
    return array[digit+8];
  else if (array[digit+9]<10)
    return array[digit+9];
  else 
    return 0;
}

int main(){
int current,position,digit,i,z;
int vet[10]={0,0,0,0,0,0,0,0,0,0};
int available[10]={0,1,2,3,4,5,6,7,8,9};

i = 9;
current = 0;
position = 0;
digit = 1;
while (i>=0){
                
  if ((current + fat(i))<=LIMIT){
    current += fat (i);
    vet[position]=digit;
    digit=digitPlus(digit,available);  
  }
  else {
    position++;
    i--;
    available[digit-1]=11;
    digit = nextDigit(available);    
  }
                printf("vet = ");
                for (z=0;z<10;z++)
                  printf("%d,",vet[z]);
                printf("n");
                printf("available = ");
                for (z=0;z<10;z++)
                  printf("%d,",available[z]);
                printf("n");
    
}
printf("final = ");
for (i=0;i<10;i++)
  printf("%d,",vet[i]);
printf("n");

return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *