学步园

        Problem Statement for TheLuckySum 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,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 }

Solution

I got a idea,every lucky num is consisted of several 4s or/and several 7s,so i think may be we can resolve it by this. Below is the my code,

getSingleLuckArray() is get lucky int [] with one lucky digit.
getLuckArray is get lucky int [] with two lucky digits, and it will invoke getSingleLuckArray(),
maybe it will get lots of int[] arrays, but we just get the array with fewest nums.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;


public class LuckySum {

    /**
     * @param args
     */
    public static void main(String[] args) 
    {
        int [] result = getLuckArray(2800);
        System.out.print('{');
        if(result != null)
        {
            for (int i = 0; i < result.length; i++) {
                System.out.print(result[i]);
                if(i!= result.length-1)
                {
                    System.out.print(',');
                }
            }
        }
        System.out.print('}');
    }

    public static int[] getLuckArray(int sum)
    {
        int [] retVal = null;
        int countOf4s = sum/4, countOf7s = sum/7;

        ArrayList result = null, temp = null;
        for (int i = countOf7s; i >=0; i--) 
        {
            for(int j=0; j<=countOf4s; j++)
            {
                if((i*7 + j*4) == sum)
                {
                    temp = new ArrayList();
                    temp.addAll(getSingleLuckArray(i*7, 7));
                    temp.addAll(getSingleLuckArray(j*4, 4));
                    if(result == null)
                    {
                        result = temp;
                    }
                    else
                    {
                        if(result.size() > temp.size())
                        {
                            result = temp;
                        }
                    }
                }
            }
        }
        if(result != null)
        {
            retVal = new int[result.size()];
            for (int i = 0; i < retVal.length; i++) {
                retVal[i] = result.get(i);
            }
            Arrays.sort(retVal);
        }
        return retVal;
    }

    public static ArrayList getSingleLuckArray(int sum, int luckDiginal)
    {
        int countOfLuckNum = sum / luckDiginal;

        int bitCount = Integer.toString(countOfLuckNum).length();
        ArrayList al = new ArrayList();
        int bitValue = 0;
        for(int i=bitCount; i>0; i--)
        {
            bitValue = getLuckNums(i, luckDiginal);
            while(true)
            {
                if(bitValue <= sum)
                {
                    al.add(bitValue);
                    sum = sum - bitValue;
                }
                else
                {
                    break;
                }
            }
        }

        return al;
    }

    public static int getLuckNums(int bitCount, int luckDiginal)
    {
        int luckNums = 0;
        StringBuffer sb = new StringBuffer();
        for(int i=bitCount; i>0; i--)
        {
            sb.append("1");
        }
        luckNums = Integer.parseInt(sb.toString()) * luckDiginal;

        return luckNums;
    }

}

It will print out "{4,7,7,7,444,777,777,777}"