P8XCoinChangeAnother | Topcoder Archive

Problem Statement

The Exponential kingdom has N types of coins. For each i from 0 to N-1, inclusive, there is a coin type worth 2^i (two to the power of i). For example, if N=3 then the coin values would be 2^0, 2^1, and 2^2.

You are given the int N and two longs coins_sum and coins_count. Your task is to find a set of coins with two properties: First, it must contain exactly coins_count coins. Second, the sum of coins it contains must be exactly equal to coins_sum. Your method must return the solution as a long[] containing exactly N elements. The i-th element of the return value must be the number of coins worth 2^i in your set. If there are multiple solutions, return the lexicographically smallest one. If there is no set that satisfies both properties, return an empty long[] instead.

Definition

Class:: P8XCoinChangeAnother
Method:: solve
Parameters:: int, long, long
Returns:: long[]
Method signature:: long[] solve(int N, long coins_sum, long coins_count)
(be sure your method is public)

Notes

Given two different long[]s A and B of equal length, let i be the smallest index such that A[i] and B[i] differ. If A[i] &lt B[i], we say that A is lexicographically smaller than B, and vice versa.

Constraints

N will be between 1 and 60, inclusive.
coins_sum and coins_count will each be between 1 and 10^18, inclusive.

Examples

```
2
```
```
4
```
```
3
```
```
Returns: {2, 1 }
```
We have N=2, which means that we can use coins worth 2^0 and coins worth 2^1. We are looking for a set of 3 coins worth 4 in total. There is a unique solution: use 2 coins worth 2^0 and 1 coin worth 2^1.
```
3
```
```
6
```
```
3
```
```
Returns: {0, 3, 0 }
```
We have N=3, which means that we can use coins worth 2^0, 2^1, and 2^2. We are looking for a set of 3 coins worth 6 in total. There are two possible solutions: 2 coins of type 0 and 1 coin of type 2, or 3 coins of type 1. Since the latter is lexicographically smaller than the former, your method should return the latter.
```
2
```
```
8
```
```
1
```
```
Returns: { }
```

10000000000

10000000000

Returns: {10000000000 }

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.