EasyPartition | Topcoder Archive

Problem Statement

Ramanujan loved partitions. And he also loved natural numbers. So, yay! He has a problem for you.

The set S consists of the first 8*N natural numbers: S = { 1, 2, 3, ..., 8*N }. You have to find a subset W of S with the following properties:

W contains exactly 2*N numbers.
The sum of W is 4*N*N.

If there is a subset W satisfying the mentioned condition, find any one such subset. Return a string of size 8*N, where the ith character (1-indexed) is '1' if i belongs to W, and '0' otherwise. Any valid solution will be accepted.

Return an empty string if it is impossible to construct a valid subset for the given N.

Definition

Class:: EasyPartition
Method:: getPartition
Parameters:: int
Returns:: String
Method signature:: String getPartition(int N)
(be sure your method is public)

Notes

W is a subset of S, hence all elements of W must be distinct.

Constraints

N will be between 1 and 50, inclusive.

Examples

```
1
```
```
Returns: "10100000"
```
W = {1,3} satisfies our conditions.
```
2
```
```
Returns: "0110110000000000"
```
4 * N * N = 16. W={2,3,5,7} Other possible solutions are {1,3,5,7}, {1,2,6,7}, {1,2,5,8} etc.
```
3
```
```
Returns: "010110110100000000000000"
```
W = {2,4,5,7,8,10} satisfies.

Returns: "01010110110101000000000000000000"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.