# [Timus] 1, 10, 100, 1000…

Problem statement is here: http://acm.timus.ru/problem.aspx?space=1&num=1209

One should note here is that ones are located at location that depends on location of previous one.

1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 …

First one is located at 1st position, second one is (1+1 = 2) position, the third one is (2+2 = 4) position, fifth one is (4+3 = 7) position and so on.

We can easily pre calculate the location of ones. This makes the problem easy to code. Here is the solution:

```package codes;

import FastIO.OutputWriter;

import java.util.HashSet;
import java.util.Set;

private Set<Long> ones = new HashSet<>();

/**
* Populate the {@code ones} set with the position of ones.
*/
long pos = 0;
long step = 1;
while (pos <= Integer.MAX_VALUE) {
pos += step;
step++;
}
}

public void solve(int testNumber, InputReader in, OutputWriter out) {
int n = in.nextInt();
StringBuilder result = new StringBuilder();
while (n-- > 0) {
int pos = in.nextInt();
// Check if the pos - 1 is in ones set, if it is then print 1
// else 0.
if (ones.contains(new Long(pos - 1))) {
result.append("1 ");
} else {
result.append("0 ");
}
}
out.println(result.toString().trim());
}
}
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.