<p>This looks like a homework assignment, so here is how to look for an answer in this kind of problems. It isn't a beautiful solution, but it's a general solution for a huge class of problems.</p>
<p>You're asking, for each index j, &quot;how many indices i <span class="math-container">$\in$</span> [1..j-1] such that a[i] &lt; X ?&quot; where X is 2a[j]. For this kind of question, there are data structures that can answer in <span class="math-container">$\log(n)$</span> time, if they have been built before. And, you're lucky, because when changing from the range [1..j-1] to the range [1..j], you can update the data structure in <span class="math-container">$\log(n)$</span> time.</p>
<p>So your algorithm is :</p>
<blockquote>
<p>Initialize data structure S</p>
<p>nbInteresting = 0</p>
<p>For each j from 1 to n:</p>
<blockquote>
<p>nbInteresting += S.request(2a[j])</p>
<p>S.add(a[j])</p>
</blockquote>
<p>return nbInteresting</p>
</blockquote>
<p>On purpose, I won't give you the exact data structure, because I guess it is the important part of the assignment, but things like binary trees are structures that work in a lot of situations.</p>
<p>Good luck !</p>

CC BY-SA 4.0
2021-01-22T10:53:45.223Z
2021-01-22T10:53:45.223Z
Hugo Manet
<p>Given array if numbers a[1..n]. Pair of numbers (i, j) is interesting, if i &lt; j и a[i] &gt; 2<em>a[j]. How to count number of interesting pairs in O(n</em>logn)?</p>
<p>What is the solution?</p>
<p>My solution is not quite O(nlogn).
Sort array and save in sorted arrau initial indices of values. For each element x of initial array find by binary search element x/2 -1 and its position in new array. Then maybe all elements that are in left part of array are possible pairs for x. Compare their indices with index of x.
Sort - nlogn.
Binary search - logn. For each element then in sum nlogn.
But comparing of indices can be n. And it will became n<em>n</em>logn.</p>

<cc.complexity-theory>
Help find algorithm for array-based task
Дарья
# Help find algorithm for array-based task

(Asked by: username_0 on 2021-01-18)

Given array if numbers a[1..n]. Pair of numbers (i, j) is interesting, if i < j и a[i] > 2*a[j]. How to count number of interesting pairs in O(n*logn)?

What is the solution?

My solution is not quite O(nlogn).
Sort array and save in sorted arrau initial indices of values. For each element x of initial array find by binary search element x/2 -1 and its position in new array. Then maybe all elements that are in left part of array are possible pairs for x. Compare their indices with index of x.
Sort - nlogn.
Binary search - logn. For each element then in sum nlogn.
But comparing of indices can be n. And it will became n*n*logn.

**Tags:** cc.complexity-theory

---

## 1 answers

### Answer by username_1 on 2021-01-22. Score: 1

This looks like a homework assignment, so here is how to look for an answer in this kind of problems. It isn't a beautiful solution, but it's a general solution for a huge class of problems.

You're asking, for each index j, "how many indices i $\in$ [1..j-1] such that a[i] < X ?" where X is 2a[j]. For this kind of question, there are data structures that can answer in $\log(n)$ time, if they have been built before. And, you're lucky, because when changing from the range [1..j-1] to the range [1..j], you can update the data structure in $\log(n)$ time.

So your algorithm is :

> Initialize data structure S
>
> nbInteresting = 0
>
> For each j from 1 to n:
>
> > nbInteresting += S.request(2a[j])
> >
> > S.add(a[j])
>
> return nbInteresting

On purpose, I won't give you the exact data structure, because I guess it is the important part of the assignment, but things like binary trees are structures that work in a lot of situations.

Good luck !


---

