Connection Status:
Competition Arena > TheSumOfLuckyNumbers

TheSumOfLuckyNumbers

SRM 403 · 2008-05-29 · by Vasyl[alphacom]

SRM 403 · 2008-05-29 · by Vasyl[alphacom] · Dynamic Programming
Class Name: TheSumOfLuckyNumbers
Return Type: int[]
Method Name: sum
Arg Types: (int)
Problem Statement

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.

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 }
4)
1000000
Returns: {4, 4, 44444, 477774, 477774 }

Submissions are judged against all 75 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TheSumOfLuckyNumbers with a public method vector<int> sum(int n) · 75 test cases · 2 s / 256 MB per case

Submitting as anonymous