CODEWITHSUNDEEP
combinations
user3134006
user3134006

Reputation: 65

from number of possible pairs get the size of the original array

I have this function

public int numberOfPossiblePairs(int n)
{
        int k=2;
        if (k>n-k) { k=n-k;}  
        int b=1;
        for (int i=1, m=n; i<=k; i++, m--)
            b=b*m/i;
        return b;
}

Which gets the number of pairs you can make from given number of items, so for example, if you have an array of 1000 items, you can make 499,500 pairs. But what I actually need is the opposite. In other words a function that would take 499500 as the parameter, and return 1000 as the original number of unique items that could produce that many pairs. (Would be a bonus if it could also handle imperfect numbers, like 499501, of which there is no number of unique items that makes exactly that many unique pairs, but it would still return 1000 as the closest since it produces 499500 pairs.)

I realize I could just incrementally loop numberOfPossiblePairs() until I see the number I am looking for, but seems like there should be an algorithmic way of doing this rather than brute forcing it like that.

Upvotes: 1

Views: 564

Answers (1)

Joseph Wood
Joseph Wood

Reputation: 7597

Your problem boils down to a little algebra and can be solved in O(1) time. We first note that your function does not give the number of permutations of pairs, but rather the number of combinations of pairs. At any rate the logic that follows can be easily altered to accommodate permutations.

We start off by writing the formula for number of combinations choose k.

enter image description here

Setting n = 1000 and r = 2 gives:

1000! / (2!(998)!) = 1000 * 999 / 2 = 499500

Just as numberOfPossiblePairs(1000) does.

Moving on in our exercise, for our example we have r = 2, thus:

total = n! / ((n - 2)! * 2!)

We now simplify:

total = (n * (n - 1)) / 2

total * 2 = n^2 - n

n^2 - n - 2 * total = 0

Now we can apply the quadratic formula to solve for n.

enter image description here

Here we have x = n, a = 1, b = -1, and c = -2 * total which give:

n = (-(-1) +/- sqrt(1^2 - 4 * 1 * (-2 * total))) / 2

Since we are only interested in positive numbers we exclude the negative solution. In code we have something like (Note, it looks like the OP is using Java and I am not an expert here... the following is C++):

int originalNumber(int total) {
    int result;
    result = (1 + std::sqrt(1 - 4 * 1 * (-2 * total))) / 2;
    return result;
}

As for the bonus question of returning the closest value if the result isn't a whole number, we could simply round the result before coercing to an integer:

int originalNumber(int total) {
    int result;
    double temp;
    temp = (1 + std::sqrt(1 - 4 * 1 * (-2 * total))) / 2;
    result = (int) std::round(temp);
    return result;
}

Now when values like 500050 are passed, the actual result is 1000.55, and the above would return 1001, whereas the first solution would return 1000.

Upvotes: 1

Related Questions