ACM (TJU) : 1150


1 ) just forget the background story (1st 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();
		}
	}
}

One thought on “ACM (TJU) : 1150

  1. // Author : unknown
    
    #include<iostream>
    using namespace std;
    
    int main ()
    {
        int n,i,t=0,f[11]={1,1,2,6,24,120,720,5040,40320,362880,3628800};
        
        while(cin>>n){
            if ( n < 0 )
                return 0;
            
            if(n==0) cout<<"NO\n";
            
            else{
                for(i=10;i>=0;i--)
                    if(n>=f[i]) n-=f[i];
                if(n==0) cout<<"YES\n";
                else cout<<"NO\n";
            }
        }
        return 0;
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s