Find number of pairs (i,j) such that i < j and A[i] >= 2A[j]

Question

The problem is to find an algorithm (preferably using the divide and conquer approach) to count the number of all ordered pairs (i,j) in an array with i < j and A[i] >= 2*A[j].

I already know an O(²) way but I want a more efficient algorithm in or log order.

This is my code in python:

ans = 0

def recursion(arr):
    global ans
    if len(arr) > 1:
        left = arr[:len(arr)//2]
        right = arr[len(arr)//2:]
        recursion(left)
        recursion(right)
        for i in left:
            for j in right:
                if i >= 2*j:
                    ans += 1

a = list(map(int, input().split()))
recursion(a)
print(ans)

Sample input: [8, 1, 9 ,4, 1]
Expected output: 6

SO is not a coding service; please provide more detail on what you have tried — miquelvir, Mar 28 '21 at 15:34
You need to compare every item to every other item (except itself maybe) - that sounds like a product which is n^2. You could use Numpy and push it down to C code but I imagine it is still O(n^2). — wwii, Mar 28 '21 at 15:49
Related:[How to compare each item in a list with the rest, only once?](https://stackoverflow.com/questions/16603282/how-to-compare-each-item-in-a-list-with-the-rest-only-once), — wwii, Mar 28 '21 at 16:01
About your code: try to avoid the use of a global variable `ans`. Instead make a function that *returns* the count. — trincot, Mar 28 '21 at 16:17

score 1 · Accepted Answer · answered Mar 28 '21 at 17:57

It's possible to make the conquer part of your code work more efficiently by sorting each array half and adapting the logic of mergesort/inversion counting. The Python code below exploits Timsort to yield a linear-time sorted merge.

BTW, I count 6 such pairs in the given input: (8, 1), (8, 4), (8, 1), (9, 4), (9, 1), (4, 1).

def merge(left, right):
    return sorted(left + right)


def recursion(arr):
    if len(arr) <= 1:
        return 0, arr
    half = len(arr) // 2
    left_ans, left = recursion(arr[:half])
    right_ans, right = recursion(arr[half:])
    cross_ans = 0
    j = 0
    for i in range(len(left)):
        while j < len(right) and left[i] >= 2 * right[j]:
            j += 1
        cross_ans += j
    return left_ans + cross_ans + right_ans, merge(left, right)


print(recursion([8, 1, 9, 4, 1])[0])

Find number of pairs (i,j) such that i < j and A[i] >= 2A[j]

1 Answers1