4

I have to make a program that finds the n-th element in the following endless sequence:

1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1......

So here you can see that 'center' increments by one and side elements of the 'center' reflect each other so we can break this sequence into small groups: 

[1][121][12321][1234321].....

So the task is to find n-th element in the sequence given n. For example, we take 7 as input and must return 3, because the 7th element in sequence is 3. The problem here is that when n exceeds 10^15 my program shows runtime error, while input can be as large as 10^100000. Here is my code:

n = int(input())
fin = n
number = long(1)
counter = long(0)
while n>0:
    n = n - number
    number = number+2
    counter = counter + 1
mid = long((counter-1)*(2+2*(counter-1))/2+1)

place = long(counter - abs(mid-fin))

if fin==0:
    print 0
else:
    print place
Gholamali Irani
  • 4,391
  • 6
  • 28
  • 59
ar kang
  • 95
  • 1
  • 9
  • 1
    What happens for *center*s greater than 9 (assuming the numbers are in base9)? In other words what is the sequence following `12345678987654321`? – CristiFati Jan 03 '18 at 13:06
  • the same pattern: 1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1 – ar kang Jan 03 '18 at 14:35

1 Answers1

7

We have groups of numbers: 

[1] [1 2 1] [1 2 3 2 1] ...

The overall amount of numbers in k groups is:

1 + 3 + 5 + ... + k*2-1

This is an arithmetic progression, its sum equals to 

(1 + k*2-1) * k / 2 = k^2

Now let's find the number of full groups k that go before n-th number in the sequence. 

k = ⌊sqrt(n-1)⌋

Now we know that our n-th number is in group number k+1 that has k*2+1 elements. Let's discard first k groups (they have k^2 numbers), now we need to find the number with index n-k^2. And its value will be equal to k+1 - |n-k^2 - (k+1)|. For relatively small n we can use this code:

n = int(input())
k = int(math.sqrt(n-1))
print(k+1 - abs(n-k*k - (k+1)))

But seeing the n <= 10^5000000 constraint we cannot simply use math.sqrt, we need other way of finding a square root of a large integer. This SO question could be helpful.

DAle
  • 8,990
  • 2
  • 26
  • 45
  • Thank you very much! But can you explain this line: k = lsqrt(n-1)l? – ar kang Jan 03 '18 at 14:49
  • @arkang, `sqrt` - is a square root of a number, `⌊x⌋` is `x` rounded down to the nearest integer – DAle Jan 03 '18 at 14:52
  • Unfortunately, this code does not work for certain inputs (which are unknown). But anyway thank you very much for the help! – ar kang Jan 03 '18 at 14:58
  • @arkang, could you please give me a link to the problem? Maybe that sequence is zero-based? – DAle Jan 03 '18 at 15:01
  • I think link to the problem will be useless, because it is not on english), but I can tell you for sure that there is nothing else in the task and the sequence is not zero based. – ar kang Jan 03 '18 at 15:08
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/162431/discussion-between-dale-and-ar-kang). – DAle Jan 03 '18 at 15:17
  • well, n is said to be 1<=n<=10^5000000, so it's not the case. – ar kang Jan 03 '18 at 15:18