I am trying to solve problem 24 https://projecteuler.net/problem=24 of the project euler and I have spent a lot of time on this problem but still no success.
But now it's not about the problem, I wanted to know what wrong with my method.
I am using simple permutation to get the leftmost digit and getting the remaining value from the term to be found (by subtracting i.e. using modulo operator).
Java Code:
import java.util.ArrayList;
public class LexOrder
{
public static int factorial(int num)
{
int res=1;
if(num <= 1)
return 1;
while(num > 1)
{
res *= num--;
}
return res;
}
public static ArrayList<Integer> addValue(int digit, ArrayList<Integer> al)
{
int temp=0, count=0;
while( count <= digit )
{
if( al.contains(count) )
temp++;
count++;
}
int val = digit+temp;
//checking weather the new number exists in the ArrayList or not.
while(true)
{
if(! al.contains(val) )
{
al.add(val);
break;
}
else
{
val++;
}
}
return al;
}
public static void main(String args[])
{
ArrayList<Integer> al = new ArrayList<Integer>();
int index = 999999;
int numOfDigit = 10;
if( factorial( numOfDigit ) > index && index >= 0)
{
System.out.println("Index Validated");
}
else
{
System.out.println("Index out of bounds");
System.exit(0);
}
int digit, count=1;
while( index !=0 )
{
digit = ( index / factorial( numOfDigit - count ) );
al = addValue(digit, al);
index = ( index % factorial( numOfDigit - count ) );
if(index == 0)
break;
count++;
}
// Adding value in ascending order.
int temp =0;
while( al.size() < numOfDigit )
{
if(!al.contains(temp))
al.add(temp);
temp++;
}
System.out.println(al);
}
}
Output: [2, 7, 8, 3, 9, 1, 4, 5, 6, 0]
Output should be: 2783915460
So without being able to walk you through the exact numbers I can tell something is off with the way you manage your digits:
int temp=0, count=0;
while( count <= digit )
{
if( al.contains(count) )
temp++;
count++;
}
int val = digit+temp;
This approach in particular fails to check whether or not some of the numbers (particularly those between digit
and digit+temp
) are already in your array list.
I was able to fix it by counting on the number of elements not used instead:
int val=0, count=0;
while( count < digit)
{ if( !al.contains(val++) )
count++;
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments