venkatesh.duggirala
BAN USERIn 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.
 venkatesh.duggirala December 21, 2015If 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;
}

venkatesh.duggirala
December 06, 2015 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++;
}
}

venkatesh.duggirala
December 06, 2015 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");
}

venkatesh.duggirala
December 06, 2015 void moveallZeros(int arr[], int arraySize)
{
int frontPointer=0;
int backPointer=arraySize1;
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".
 venkatesh.duggirala November 19, 2015
Repmarthajpatton, Data Scientist at AppPerfect
Managed a small team implementing gravy in Prescott, AZ. Developed several new methods for easy break up spells.Had some ...
Reprohitrana0777, Animator at AMD
I am work in free lancing as a editor in web developer. I also like play sports. I like kabaddi ...
Open Chat in New Window
I have exactly the similar idea and before posting it wanted to search if it exists here:), cool, it is there.
 venkatesh.duggirala December 21, 2015