1
votes

I want to find a number[i] of infinite sequence but it takes a long time in the following input.

Let's consider an infinite sequence of digits constructed of ascending powers of 10 written one after another. Here is the beginning of the sequence: 110100100010000... You are to find out what digit is located at the definite position of the sequence.

Input There is the only integer N in the first line (1 ≤ N ≤ 65535). The i-th of N left lines contains the integer K[i] — the number of position in the sequence (1 ≤ K[i] ≤ 231 − 1).

Output You are to output N digits 0 or 1 separated with a space. More precisely, the i-th digit of output is to be equal to the Ki-th digit of described above sequence.

INPUT

4 
3
14
7
6

OUTPUT

0 0 1 0

Here's my code

x = input()
a = []
for i in range(x):
    y = input()
    a.append(y)

b = '1'
c = 1
for i in range(100):
    c *= 10
    b += str(c)

for i in range(x):
    print b[a[i]-1],
3
and the question is ? - Tony Suffolk 66
@jonrsharpe I suppose the problem here is that K[i] can be a lot larger (1 ≤ K[i] ≤ 231 − 1, where I assume "231" is a copy-and-paste error and means 2^31) and the approach of this program doesn't hold. - Carsten
The trick here is noticing that there aren't very many ones, and you can work out exactly where they'll be based on the pattern; anything else must be a zero. You can write a function to determine, for given i, whatK[i] must be without building the string. - jonrsharpe

3 Answers

1
votes

You need to go beyond the basic description of the problem. If you generate the whole string, that'll be 2^31 characters long (and you'll need to go up to 65536, not 100). Fortunately, there is a better way. You don't really need the string. You just need a method to check if the character at a given index K[i] is 1.

The positions of all "1"s in the string correspond to the triangular numbers. The nth triangular number can be calculated via

x = n * (n + 1) / 2

By solving for n, we get

n = sqrt(2 * x + 0.25) - 0.5

If x is a triangular number, then n will be an integer, and the string will have a "1" on that position. Otherwise, a "0". Also, we have to use K[i] - 1, because the index in the problem is 1-based.

import math
import sys

f = lambda x: math.sqrt(2.0 * x + 0.25) - 0.5
g = lambda x: f(x) % 1 == 0

inp = map(int, sys.stdin.read().split()[1:])

print(" ".join("1" if g(x-1) else "0" for x in inp))
1
votes

You should not generate a whole string here, rather than that use some maths. Here the numbers will be:

1
10
100
1000
10000
...

If you look at the series you'll notice that the 1's are at the position 1, 2, 4, 7, 11, .... We can generalize this series using this formula (n^2 - n + 2)/2. So, the quadratic equation will become:

(n^2 - n + 2)/2 = i
#or n^2 - n + 2 - 2i

Where i is the current index coming from input.

Now, if for any i the output of b^2 - 4ac is a perfect square then it means the number is surely 1 otherwise it's 0.(Here value of a is 1, and b is -1 and we can calculate c using 2 - 2*i)

from math import sqrt

def solve(i):
    b = -1
    a = 1
    c = 2 - 2 * i
    val = (b**2) - (4*a*c)
    sq = sqrt(val)
    if int(sq) == sq:
        return 1
    return 0

for _ in xrange(input()):
    print solve(input()),

Demo:

$ python so.py < foo.txt 
0 0 1 0
0
votes

It maybe take a lot of time because you are constructing the complete sequence of digits of ascending powers of 10. If you analyze the structure of the sequence you can notice some patter.

The patter in combination with the fact sum_{i=1}^n = (n+1)*n/2 gives the next solution, where the function digit_pow_10 can determinate directly if the digit in the position y is 1 or 0, without construction the complete sequence. If you need more details please contact me

import math

def digit_pow_10(y):
    n = int(math.sqrt(0.25+2*y)-0.5)
    diff = y - int(n*(n+1)/2.0)
    if diff == 1 or y == 1:
        return 1
    else:
        return 0

x = input()
for i in range(x):
    y = input()
    a.append(y)

for y in a:
    print digit_pow_10(y),