CODEWITHSUNDEEP
algorithm
texaspete11
texaspete11

Reputation: 43

Finding two integers appearing in all pairs

I recently came across this question and cannot come up with a good solution.

You are given m pairs of integers. Each integer is between 1 and n, inclusive. Find two integers x and y (1 <= x < y <= n) such that in each pair at least one integer is equal to x OR y.

For example, give (1,2) (2,3) (3,4) (4,5) the integers would be 2,4

It seem like there should be a O(n) solution but all I have come up with is an awful brut force attempt.

pair<int, int> AwefulPairFinding(vector< pair<int,int> > pairs)
{
    vector<int> vec;

    for(const auto& p : pairs)
    {
        vec.push_back(p.first);
        vec.push_back(p.second);
    }
    //remove duplicates
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    // test pairs
    for (auto j = 0; j < vec.size(); j++)
    {
        for (auto k = j+1; k < vec.size()-1; k++)
        {
            if (2 == vec[j] && 4 == vec[k])
                cout << "";
            int matches = 0;
            for (const auto& p : pairs)
            {
                if (p.first == vec[j] || p.second == vec[j] || p.first == vec[k] || p.second == vec[k])
                    ++matches;
                else
                    break;
            }
            if (matches == pairs.size())
                return make_pair(vec[j], vec[k]);
        }
    }
    return make_pair(0, 0);    
}

Upvotes: 0

Views: 248

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58271

Take the first pair in your list, say (a, b). Search through the remaining pairs for one that's distinct. If you didn't find one, (a, b) is a pair of integers that intersects with every other pair and you're done. If you did find one, say (c, d), then you have only four possibilities for the two integers: (a, c), (a, d), (b, c), (b, d). Go through the all the pairs, and see if any of these four possibilities work.

This is clearly O(n) since you go through all the pairs twice, and perform a bounded amount of work on each.

Note: If your pairs can be equal, and you have an equal pair (a, a), then a must be one of the two integers. Find the other integer by seeing if there's any value in common with the remaining pairs that don't contain an a. Note that as soon as you find a pair that doesn't contain a there can be only 2 choices (or 1 if it's also paired). (Actually, with careful coding, this paired case falls under the first case, except you have to be careful never to choose (a, a) as your two integers).

Here's some example Python code that doesn't try to be efficient, and doesn't handle the edge-case of returning the same integer twice if that integer is a cover (under some circumstances). It runs in O(n) time though.

def distinct(p, q):
    return p[0] != q[0] and p[0] != q[1] and p[1] != q[0] and p[1] != q[1]

def find_2cover(ps):
    c, d = None, None
    for q in ps:
        if distinct(ps[0], q):
            c, d = q
            break
    else:
        return ps[0]
    a, b = ps[0]
    choices = [(a, c), (a, d), (b, c), (b, d)]
    for q in ps:
        remove = []
        for c in choices:
            if distinct(q, c):
                remove.append(c)
        if remove:
            choices = [c for c in choices if c not in remove]
    return choices[0] if choices else None


print(find_2cover([(1,2), (2,3), (3,4), (4,5)]))

Output:

(2, 4)

Upvotes: 3

Related Questions