TopCoder Statistics - Problem Statement

Problem Statement

A partition of the number n is the set of numbers that all sum up to n. For example, we have 5 different partitions of 4: {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}, {4}. If we sort all the numbers within each set, we can treat each partition as a sorted list of numbers and so introduce a lexicographic order on all partitions. For example, the partitions of 4 mentioned before are given in order. You are given ints n and k. Determine all the partitions of n, sort them in lexicographical order, and return a int[] containing the k-th one (k is a 1-based index). If there are not enough partitions of n, return an empty int[].

Definition

Class:: NumberPartition
Method:: kthPartition
Parameters:: int, int
Returns:: int[]
Method signature:: int[] kthPartition(int n, int k)
(be sure your method is public)

Notes

The lexicographical order is exactly the same as in a dictionary. A int[] A is lexicographically before a int[] B if there exists an integer i such that A[i] < B[i] and A[j] = B[j] for all j < i or if A is a proper prefix of B.

Constraints

n will be between 1 and 50, inclusive.
k will be between 1 and 1000000, inclusive.

Examples

4

1

Returns: {1, 1, 1, 1 }

Example from the problem statement.
4

3

Returns: {1, 3 }
17

123

Returns: {1, 1, 1, 3, 3, 3, 5 }
12

1234

Returns: { }

There are less then 1234 partitions of 12.
23

1234

Returns: {4, 19 }
50

1

Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
50

2

Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2 }
50

204226

Returns: {50 }
50

204227

Returns: { }
50

200000

Returns: {3, 4, 5, 5, 5, 28 }
50

204200

Returns: {13, 16, 21 }
47

123456

Returns: {4, 5, 5, 5, 7, 7, 7, 7 }
43

12342

Returns: {1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 6, 6 }
23

42354

Returns: { }
45

23434

Returns: {1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4, 6, 6, 15 }
43

59999

Returns: {2, 4, 7, 7, 11, 12 }
11

32

Returns: {1, 2, 2, 2, 4 }
32

8222

Returns: {4, 5, 9, 14 }
49

159567

Returns: {2, 2, 3, 5, 11, 13, 13 }
47

59999

Returns: {1, 1, 1, 1, 2, 4, 7, 7, 11, 12 }
17

234

Returns: {2, 2, 2, 2, 2, 3, 4 }
45

14253

Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 7, 19 }
46

48230

Returns: {1, 1, 1, 1, 2, 2, 3, 4, 5, 5, 5, 7, 9 }
23

5343

Returns: { }
43

60454

Returns: {3, 3, 3, 3, 3, 3, 3, 3, 6, 13 }
43

62497

Returns: {4, 4, 11, 12, 12 }
7

24

Returns: { }
7

11

Returns: {1, 6 }
7

5

Returns: {1, 1, 1, 4 }
39

1234

Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 19 }
41

40431

Returns: {2, 2, 3, 4, 8, 22 }
50

27

Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3 }
1

1

Returns: {1 }
1

1000000

Returns: { }
50

1000000

Returns: { }
2

1

Returns: {1, 1 }
2

2

Returns: {2 }
3

1

Returns: {1, 1, 1 }
3

2

Returns: {1, 2 }
3

3

Returns: {3 }
4

2

Returns: {1, 1, 2 }
4

4

Returns: {2, 2 }
4

5

Returns: {4 }
50

54321

Returns: {1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 4, 7, 10, 10 }
50

10000

Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 5, 12, 12 }

Statistics

Problem Statement for "NumberPartition"

Problem Statement

Definition

Notes

Constraints

Examples