EveryoneLovesMicrosoft
BAN USERFisher–Yates shuffle (aka Knuth Shuffle)
measure occurrances of each perumation over a large testcase...
ignore my previous post...
(untested)
void binarySrch(int a[],int lb, int ub, int key)
{
if( a[lb] > key || a[ub] < key) return -1; //doesn't exit in range
while( lb < ub)
{
int mid = lb + (ub-lb)>>1; // (lb+ub)/2 = integer overflow
if( a[mid] == key)
{
if( mid!=0 && a[mid-1] == key)
ub = mid - 1;
else
return mid
}else
if(a[mid] < key)
lb = mid+1
else
ub = mid-1;
}
return -1;
}
for 2 unsorted arrays...
LOLer is Right. O( (n+m) log n)
where m,n are size of 2 arrays, and m > n.
if atleast one is sorted O(mlogn)
if both are sorted O(m+n) (FYI, you could use O(mlogn) too)
If the Numbers are given DISTINCT, then this'll work
1) sort array a
2) first = 0, last = a.size()-1
3) while ( first < last)
3.0) sum = a[first] + a[last]
3.1) if(sum == k )
3.15) printf a[first],a[last]
3.2) first++;
3.3) last--;
3.4) else
3.5) if ( sum > k) last--;
3.6) else first++;
4) end
@amit, you're correct. :) that'll work....but how about this...
int intersect(int a[],int uba,int b[],int ubb,int c[]) //c is atleast uba+ubb...returns ubc
{
int lba = 0, lbb = 0, lbc = 0;
while( (lba < uba) && (lbb < ubb))
{
if( a[lba] == b[lbb])
{
int t = a[lba];
while(a[lba] == t) lba++;
while(b[lbb] == t) lbb++;
c[lbc++] = t;
}else
if( a[lba] < b[lbb])
lba++;
else
lbb++;
}
return lbc;
}
If i can choose my language, i choose Python (supports BigNum by default) :)
- EveryoneLovesMicrosoft October 30, 2009
You could do this bit by bit or nibble by nibble...or even byte by byte (look up table)
- EveryoneLovesMicrosoft November 03, 2009