CareerCup

#include <set>
#include <utility>
#include <iostream>

typedef std::set<std::pair<int, int>> PairOfNums;

void findNotMachingPairs(int n, PairOfNums& s)
{
    // at least 2 numbers needed
    if (n >= 2) {
        for (int a = 1; a <= n - 1; ++a) {
            for (int b = 2; b <= n; ++b) {
                if (a > 10 * b || b > 10 * a) s.insert(std::make_pair(a, b));
            }
        }
    }
}

int main()
{
    int n = 40;

    PairOfNums s;
    findNotMachingPairs(n, s);

    for (PairOfNums::const_iterator it = s.begin(); it != s.end(); ++it) 
    {
        std::cout << (*it).first << " " << (*it).second << "\n";
    }    
 
    return 0;
}

If i understand problem correctly and we need to form a set of violating pairs, we just need to loop over range 1..n and for each number 'a' add to set pairs of form {a, b}, where b is in range 1..n excluding ceil(a/10.0) .. a*10.

I think we should sort the numbers, then for each i we can do a binary search for array[i]×10.. if we found a match then we have a pair a,b.. if no match was found our modified binary search should return the largest number smaller than array[i]×10.. if that number is not the array[i] then a match is found.. else do the same for the next array elements

R we just looking for pairs which have different digits?

like 10,3;10,110
we can reduce the search space by this.

int set[0]=a[0];
int count=0;

for(int i=0;i<n;i++)
{
if(a[i]>10*set[count])
{
count++;
set[count]=a[i]
}

i++;
}

//assuming that we have to find the largest set which fulfills all the conditions.

On first thought, it would seem THE PROBLEM itself has an OMEGA(N^2) runtime (lower bound N^2).

The number of pairs that meet the conditions of the question seems to be ( as N-> inf ) quadratic in N. So you have to access all results.

Or am I missing anything?

s = [(a,b) for a in range(n) for b in range(n) if a>10*b or b>10*a]

don't we have all no.s from 1 to n or just some of the numbers ????