TopCoder problem "TheSumOfLuckyNumbers" used in SRM 403 (Division II Level Three)



Problem Statement

    

John thinks 4 and 7 are lucky digits, and all other digits are not lucky. A lucky number is a number that contains only lucky digits in decimal notation.

Some numbers can be represented as a sum of only lucky numbers. Given an int n, return a int[] whose elements sum to exactly n. Each element of the int[] must be a lucky number. If there are multiple solutions, only consider those that contain the minimum possible number of elements, and return the one among those that comes earliest lexicographically. A int[] a1 comes before a int[] a2 lexicographically if a1 contains a smaller number at the first position where they differ. If n cannot be represented as a sum of lucky numbers, return an empty int[] instead.

 

Definition

    
Class:TheSumOfLuckyNumbers
Method:sum
Parameters:int
Returns:int[]
Method signature:int[] sum(int n)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 1,000,000, inclusive.
 

Examples

0)
    
11
Returns: {4, 7 }
It is simple: 11 = 4 + 7.
1)
    
12
Returns: {4, 4, 4 }
Now we need three summands to get 12.
2)
    
13
Returns: { }
And now we can not get 13 at all.
3)
    
100
Returns: {4, 4, 4, 44, 44 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8571

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12175&pm=8571

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Dynamic Programming