CODEWITHSUNDEEP
c++algorithm
ebvtrnog
ebvtrnog

Reputation: 4377

Clever way to calculate position in an array (C++)

For the sake of performance, in a O(n^2) algorithm I want to lower the complexity by a factor of two. Basically, I have a structure of this shape:

0   1   2   3   4   5
----------------------
0                     | 1
1,  2                 | 2
3,  4,  5             | 3
6,  7,  8,  9         | 4
10, 11, 12, 13, 14    | 5
15, 16, 17, 18, 19, 20| 6

Thus I created a vector of size ((1+n)*n/2) - obviously, the arithmetic sum. The thing is that I need now to calculate each position back and forth. As an example, if I want to calculate the position in the column 2 and row 5 I can calculate it like this:

int get_position(int x, int y)
{
    int smaller = min(x, y);
    int greater = max(x, y);
    return ((1 + greater) * greater / 2) - greater + smaller;
}

The question is: how can I calculate it the way back? In other words, for example from position no. 17 I would like to get 2 and 6.

Or, maybe there is some better way to do it in C++? (some structure would make it easy)

EDIT I am looking for a way to calculate this in O(1). Does it exist?

Upvotes: 3

Views: 163

Answers (3)

undur_gongor
undur_gongor

Reputation: 15954

Yes, an O(1) solution does exist.

Mathematically, the bigger index is:

i = [sqrt(2n + 1/4) + 1/2]

(square brackets "[]" denoting truncation to integer).

It might be difficult to correctly calculate this in floating point, though.

The smaller index is then:

j = n - i*(i-1) / 2

Upvotes: 5

Ation
Ation

Reputation: 731

First of all - with your indexing 'y' will be always bigger than 'x', so you could remove min function calls. To get (x,y) pair from index - there will be two steps:

y = (integer solution to (index) = (y+1)*y / 2) + 1
x = index - y*(y+1)/2

Upvotes: 2

Joshua Byer
Joshua Byer

Reputation: 519

This is not N squared since we can eliminate entire arrays going down and than search through the correct array using pivots.
First we check the first number of each array and wait for it to N to be between arri[0] and arri+1[0].
After that you can use the Binary search algorithm to find the correct number in the array.
Binary search is log n, and I can't offhand tell you the runtime of the first portion but I am guessing log n. As such this operation can be done in log n time

Upvotes: 0

Related Questions