CODEWITHSUNDEEP
algorithmdistinct
kamui
kamui

Reputation: 1

counting number of distinct pairs such that i<j and A[i] =/= A[j]

I'm trying to solve this in O(n log n) time. Given a sorted array A, how can I determine the number of distinct pairs with the requirements i < j and A[i] and A[j] be different numbers?

An example would be A = [1, 2, 3, 3], distinct pairs would be (1,2), (1,3), (2,3) returning 3.

Upvotes: 0

Views: 724

Answers (1)

MBo
MBo

Reputation: 80325

Scan array left to right to find unique elements count

if (A[i] != A[i-1])
    uniq_count++

Note that time is linear O(n)

For the number of unique elements M number of pairs is

M*(M-1)/2

Why? The first element forms M-1 pairs with tne next elements. The second one forms M-2 pairs (one has been already counted) and so on. Result is sum of aritmetic progression.

Upvotes: 4

Related Questions