CareerCup

I have exactly the similar idea and before posting it wanted to search if it exists here:), cool, it is there.

In my case, the number of comparisons between the set members are zero. But ofcourse the time penalty is somewhere else (finding out next value), hence the time complexity is almost same.

If interviewer says that "Do it faster than O(N^2), N= 2^K", then I feel that he is giving me a clue, do not think too hard to come up with a O(N) solution, just an algorithm that does not involve comparing each pair will satisfy him.

Hence I am thinking in the following lines

Lets assume there is a function that gives us next higher possible value that satisfies the condition i.e., a> b and a & b == a, then we can write code like

for (all 'a' s in the given set)
 { 
        int i=0;
        while ( b < maxValueoftheSet)
        {
           b= Give_me_i_th_next_of(a)
           if ( b is part of the set ) 
             print (a, b);
        }
 }

For the part of "b is part of given set" , can be done in O(1) many ways , provided that we have enough space , for eg: hash table(std::map)

Now coming to the main part implementation of Give_me_i_th_next_of(a) in O(1)

1) Lets say you identified number of '0's in the binary representation and lets assume
lets say K=8 and a= 10100110=> 7th, 5th, 4th, 1st bits are '0's.
changing these four bits (7th, 5th, 4th and 1st) to
0001 will give 1st next value,
0010 will give 2nd next value
0011 will give 3rd next value
.....
1111 will give me 15th next value.

We can implement Give_me_i_th_next_of(a) in O(1) and while loop will repeat for
2 ^ (number of zero bits)

lets assume avg number of zero bits in all the numbers is z which will be < k

Order of the algorithm : ( 2 ^ k ) * ( 2 ^ z) which is less ( 2 ^ K) * ( 2 ^ K )

Please let me know if you have any opinions on this algorithm.

/**
   @return sorted(arr[a:b])[k]
   @complexity: runtime - O(n)
                space   - O(n)
*/
int processRequest(int A[], int size, int a, int b, int k)
{
  int tempArray[size];
  memset(tempArray, 0, sizeof(tempArray));
  for(int i=a; i<=b; i++)
    tempArray[A[i]]=1;   
              
  for (int i=0; i< size; i++)
  {
    if (tempArray[i])
    {
      if (!k)
        return i;
      k--;
    }
  }
  return -1;
}

void printPairs(int a[], int len, int givenDiff)
{
    int i=0, j=1;
    while (j <len)
    {
      if (a[j] - a[i] == givenDiff)
        printf("Pairs : [ %d %d ]\n", a[i++], a[j++]);
      else if (a[j] - a[i] < givenDiff)
        j++;
      else
        i++;
    }
}

Please run your code by remove 2 from the array.
3 and 6 pair will be missed due to small bug in your code.
I am pasting my code at the end , you can see it just in case if you cannot make it.
But I am sure you can fix it.

#include<iostream>

bool subArray(int A[], int sumValue, int n, int * sI, int *eI)
{
  int i=0;
  *sI=0;
  int sum= A[0];
  while (i< n)
  {
    if (sum == sumValue)
    {
      *eI= i;
      return true;
    }
    else if (sum > sumValue)
    {
      sum= sum - A[*sI];
      (*sI)++;
    }
    else
    {
      i++;
      sum= sum +  A[i];
    }     
  }
  return false;
}

int main()
{
   int A[]= {2, 3, 1, 5, 4, 6, 7};
   int len= sizeof(A)/sizeof(int);
  int sI, eI;
   if (subArray(A, 28, len, &sI, &eI))
   {
     for(int i=sI; i<=eI; i++)
       printf("%d value\n", A[i]);
   }
   else
     printf("Not fund such subArray\n");  
}

void moveallZeros(int arr[], int arraySize)
{
int frontPointer=0;
int backPointer=arraySize-1;
while (frontPointer < backPointer)
{
while(arr[frontPointer] != 0 && frontPointer < backPointer)
{
printf("%d incrementing fp\n", frontPointer);
frontPointer++;
}
while(arr[backPointer] ==0 && frontPointer < backPointer)
{
printf("%d incrementing fp\n", backPointer);
backPointer--;
}
if (frontPointer < backPointer)
{
swap(arr, frontPointer, backPointer);
frontPointer++;
backPointer--;
}
}
}

@Mailman: Your code is correct. But I want to mention that your code/logic can be reduced as the question already says "Unique elements in T".