Great solution, So Sui Ming, I did not think about that one in particular.

I just use prefix sums and binary search.

If you write down the sequence and it's index starting from 1.

You will notice that if you do prefix sum ( half interval way , so starting from 0, the first element, first element + second element, etc. ) up till  sum <= MAX ( 2^31 - 1 ), you will get 65535 numbers in a sorted way.

In this way, notice, that the numbers in this prefix_sum array are all index s.t. digit = 1.

You still need to +1 in every position of prefix_sum array, because of 1-index of input.

Now you read input number K and do binary search on the prefix sum array.

If you did find, great! It is 1.
Otherwise, it is 0.

Thanks for the hint. I tried a very similar algorithm but was still getting WA on Test 3 in Java. I finally switched over to Python, and got AC

How ( -b +- sqrt( b^2 - 4ac ) )/2a transforms into -1 +- sqrt( 8p-7 ) / 2 ?

I do it like this:

the n-th '1'should be here: n(n-1)/2+1.So, we judge whether the input number(x) == (n(n-1)/2+1).

it could be transformed to 2*x-2 == n(n-1), and int(sqrt(2*x-2)) must be the number 'n' if 'n' exists!

How can i upgrade my ints to double ? Sorry for my ignorance.I'm a newbie...

thanks

vi apnar analysis deikha chudna hoia gelam, airokom chinta kamne ashe mathai

My initial approach was slightly different, but at the end, it gave the same result.

Here's the sequence ->
1 10 100 1000 10000 100000 ...

In that sequence, 1s are located at position ->
1, 2 ,4, 7, 11 , 16, 22 ...

Look at the 11th position in the sequence. There are total (1+2+3) zeros and (1 + 1 + 1 +1) ones before the 11th 1.  So the position no 11 can be written as the sum:
(1+2+3) + 4 x 1 + 1.

Take another position as example, say 16. Before the 16th position, there are total (1+2+3+4) zeros, and (1+1+1+1+1) ones. And so 16 can be written as,
(1+ 2+3+4) + 5 x 1 + 1.

Now if you generalize this observation and formulate it, you'll get :
n(n+1)/2 + (n+1) x 1 + 1 = (position no containing 1)

After simplification, the equation stands:
n^2 + 3n + (4 - 2 x Position No) = 0

So for any INTEGER value of n, you'll get a Position No for 1 .

Now think the opposite of this . If the Position No contains 1, then n will must have an Integer value. Otherwise, the Position No will contains 0.
Solving that equation, you'll get:

n = ( -3 +- sqrt( 9 - 4 x 1 x (4 - 2 x Position No))  ) / 2

For n to be an Integer, the determinant (9 - 4x(4 - 2 x Position No))  or (8 x Position No - 7) must be a square number.

Thanks a ton <3

This an O(log n), because the sqrt function is O(log n)

n=int(input())
numbers=[]
for i in range(0,n):
    numbers.append(int(input()))

print_s = ''

for n in numbers:
    if len(print_s) > 0:
        print_s += ' '
    length = 1
    while n > length:
        n -= length
        length += 1
    print_s += '1' if n == 1 else '0'
print(print_s)

I had the same mistake. But I used long long and it went away

8*n-7 <--- integer overflow