MagicCandy | Topcoder Archive

Problem Statement

Today is the Christmas Eve. People around the world celebrate this holiday. The following story takes place in the land of reindeer, where Santa Claus resides.

The reindeer love candies. They have n pieces of candy. The pieces of candy are numbered 1 through n. Dasher is one of the reindeer. He wants to eat one of the candies. To pick the one he will eat, Dasher uses the following method:

While there is more than one piece of candy:
Discard all candies that are numbered by perfect squares (i.e., candies 1, 4, 9, 16, 25, etc.).
Relabel the remaining k candies 1 through k, keeping the numbers in the same order.
Once only one piece of candy remains, Dasher will eat it.

You are given an int n. Your method must compute and return the number initially assigned to the piece of candy eaten by Dasher.

Definition

Class:: MagicCandy
Method:: whichOne
Parameters:: int
Returns:: int
Method signature:: int whichOne(int n)
(be sure your method is public)

Notes

It can be proved that Dasher's method will always lead to a situation in which only one piece of candy remains.

Constraints

n will be between 1 and 1,000,000,000 inclusive.

Examples

```
5
```
```
Returns: 5
```
We start with 5 candies. Let's call them A, B, C, D, and E. Initially, they are numbered 1 through 5, in this order. In the first round, we discard candies with numbers 1 (which is A) and 4 (which is D). This leaves us with candies B, C, and E. These candies now get new numbers: B becomes 1, C becomes 2, and E becomes 3. In the second round, we discard candy number 1 (which is now B). This leaves us with candies C and E. Again, the candies now get new numbers: C becomes 1 and E becomes 2. In the third round, we discard candy number 1 (which is now C). The only remaining candy is E. Its number in the beginning was 5, therefore our method should return 5.
```
9
```
```
Returns: 7
```
This time we start with 9 pieces of candy. If we label them A through I, the process will look as follows: start: ABCDEFGHI throw away candies 1, 4, 9 (A, D, I) after the first round: BCEFGH throw away candies 1, 4 (B, F) after the second round: CEGH throw away candies 1, 4 (C, H) after the third round: EG throw away candy 1 (E) at the end: G
```
20
```
```
Returns: 17
```
```
5265
```
```
Returns: 5257
```
```
20111223
```
```
Returns: 20110741
```
```
1
```
```
Returns: 1
```

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.