CODEWITHSUNDEEP
algorithmmathmathematical-optimization
Rajat kashyap
Rajat kashyap

Reputation: 622

How to find the formula of a series

I've recently faced a problem.

Problem =>

Given n, k, we have to find out the number at kth index in the series. (Series is not given we have to logically generate it to find the kth element from series)

For series pattern please take a look of example.

(Index is starting from 1 not from 0).

example =>

n=4, k=5
series = 1, 2, 3, 4, 1, 2, 3, 1, 2, 1
answer = 1 (because it is at 5th index, index is from 1).

example=>

n=5, k=8
series = 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 3, 1, 2, 1
answer=3 (because 3 is at 8th index).

I want to do this in O(1) time complexity. Is there any formula or something else to do this ?

Upvotes: 1

Views: 184

Answers (2)

M Oehm
M Oehm

Reputation: 29126

Your series can be organized in a triangle, for example for n = 4:

1  2  3  4          1  2  3  4
1  2  3             5  6  7
1  2                8  9 
1                  10

(Valuees are to the left, indices k to the right. The index k must be in [1; N] where N = n · (n + 1) / 2].) You can invert the triangle:

1                  10                   0
1  2                8  9                1  2
1  2  3             5  6  7             3  4  5
1  2  3  4          1  2  3  4          6  7  8  10

To the far right are the zero-based indices of the inverted series. The first number in each row i is the triangular number T(i) = i · (i + 1) / 2.

You can find the (zero-based) row i of the inverted triangle with

    i = floor(−½ + math.sqrt(½ + 2·(N − k)))

The first index on that row is

    T = T(i) = i · (i + 1) / 2

From that starting index T and the search index in the inverted triangle, N − k, you can get your value, but you must start counting from the end of that row:

    res(n, k) = i + 1 − (N − k − T)

I'm sorry that the exmplanation is a bit muddled by repeated reversals and switching from one-based to zero-based indexing and vice versa. Here's some Python code that implements the above:

def value(n, k):
    N = n * (n + 1) // 2            # length of series
    K = N - k                       # inverted index, zero-based
    
    i = int(-1 + math.sqrt(1 + 8*K)) // 2
    T = i * (i + 1) // 2            # row and its starting index
    
    return i + 1 - (K - T)

Upvotes: 3

Gijs Den Hollander
Gijs Den Hollander

Reputation: 723

I don't know there might be a formula out there, but you should probably ask this on the math forum.

I would do something in the following lines:

while(K > N) {
 K= K - N
 N=N-1;
}

Here K would be your answer when the while stops. It is no formula, but should be faster then generating the array and taking kth index.

Upvotes: 2

Related Questions