1 ) just forget the background story (1^{st} para)

2 ) Given a number non-negative integer n

we need to find out whether it can be expressed as a sum of factorials

3 ) n <= 1000000. so, its enough to increase our search space up to factorial 9

9! = 362880

10! = 3628800 // redundant

I’ve used just for safety

4 ) make an integer array of 10 elements

and fill it with factorials from 0 to 9

factorialArray [10] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };

5 ) try to make n, with different combination of factorialArray’ element.

There are total 1023 combinations possible.

0000000001

0000000010

0000000011

0000000100

.

.

.

.

1111111111

Here 0001110010 means,

a combination with array Index : 4, 5, 6, 9 (started from 1)

You can check all of those possible combination to find the result. And surely it can be done within time + memory limit.

6 ) Look at the factorialArray closely. There is no use to check all the combination with number 362880, if n is less than 362880.

n = X + 362880 ( when n < 362880 and X = non-negative integer ) // this is not possible.

7 ) with this idea what I’ve done, loop through the factorialArray from backward. And if a number is greater than or equals to n, then n is decreased by that number.

At the end, if n is zero then, n can be made with different combination of factorialArray’s element.

8 ) Input will terminate with a Negative number, not with -1 always.

Java Source Code:

package volume_II;
import java.util.Scanner;
public class Id_1150 {
public static void main(String[] args) {
Scanner input = new Scanner (System.in);
int array [] = {1, 1, 2, 6, 24, 120, 720, 5040,40320, 362880, 3628800};
int x = input.nextInt();
while ( x >= 0 ) {
if ( x == 0 ) {
System.out.println ("NO");
x = input.nextInt();
continue;
}
for ( int i = 10; i >= 0; i-- ) {
if ( array [i] <= x )
x -= array [i];
}
if ( x == 0 )
System.out.println ("YES");
else
System.out.println ("NO");
x = input.nextInt();
}
}
}

### Like this:

Like Loading...

*Related*

## Published by Shahab

Completed B.Sc in CSE, @United International University, Dhaka.
Currently working as Development Engineer, Android and iOS Application.
View all posts by Shahab

## One thought on “ACM (TJU) : 1150”