Skip to main content
GameDev.net gamedev.net
🔒 Locked

A hard problem! Get maximum one of two natural numbers.

Started by xmllmx Feb 12, 2006 at 8:06 PM 221 replies 46.6k views
Original Post
xmllmx
xmllmx
Problem: Write a function which accepts two natural numbers (unsigned int) and return the maximum one. Requirement: In the function body, You may not use any comparing operation, such as <, >, ?:, if, switch, etc. In other words, Only these operators of {+, -, *, /} can be used, any other operator or function call is invalid! Who is interested in this and can solve it? unsigned int Max(unsigned int a, unsigned int b) { // Add your code here! } [Edited by - xmllmx on February 12, 2006 8:49:49 PM]
xmllmx
xmllmx
The problem is given to the interviewees by a noted game company.
knowyourrole
knowyourrole
well... I hope I dont get that in any interview =s

I'm a little stumped currently
sjelkjd
sjelkjd 
unsigned int Max(unsigned int a, unsigned int b){  int max = 0xFFFFFFFFU;  vector<vector<unsigned int> > foo(max, vector<unsigned int>(max,0));  for(unsigned int i=0;i<=max;i++)   {    for(unsigned int j=i+1;j<=max;j++) foo[j] = b;    for(unsigned int j=0;j<i;j++) foo[j] = a;    foo = a;  }  return foo[a];}

And since I used a lookup table, it'll be faster than any arithmetic evaluations!
xmllmx
xmllmx
The solution upstairs cannot be accepted!

1, It cannot get the correct result;

2, It is too time-consuming!

3, Any Iteration Statement(while, do-while, for, and the like) is not permitted.
DaBono
DaBono
Quote:
Original post by sjelkjd
int max = 0xFFFFFFFFU;
vector > foo(max, vector(max,0));

And wouldn't these two lines request 2^32 * 2^32 * 4 bytes = 73 million TB of data?
poss74
poss74
Well I'm stumped.

The answer's going to be really simple, and we'll all kick ourselves for not spotting it first.

You're an evil person, xmllmx: this thing's going to keep me at it for a while.....
If at first you don't succeed, call it version 1.0You don't stop playing because you get old; you get old when you stop playing.
DaBono
DaBono
Oh, do things like std::sort fall in the comparison category? If not, my solution:
unsigned int maxTheRoughWay( unsigned int a, unsigned int b ) {  std::vector<unsigned int> numbers;  numbers.push_back(a);  numbers.push_back(b);  std::sort( numbers.begin(), numbers.end() );  return numbers[1];}
xmllmx
xmllmx
I must put an additional requirement on it:

Any function call is not permitted!

You may not use any functions provided by the compiler, including STL functions.
Trapper Zoid
Trapper Zoid
I'm fairly rusty in programming still, but I'll give this a shot [smile].

unsigned int Max(unsigned int a, unsigned int b){       // I'm assuming these are *natural* numbers, i.e. non-negative   unsigned int comp1 = (b / a);     // should be zero if a > b   unsigned int comp2 = (a / b);     // should be zero if b > a   return a * (comp1 == -comp1) + b * (comp2 == -comp2);}


Edit: Dang, I keep getting the order of a and b messed up...
Edit 2: Not sure if the == comparison is allowed [grin], but I could probably think of a hack around that...
nilkn
nilkn 
unsigned int Max(unsigned int a, unsigned int b){     unsigned int diff = abs(a - b);     return (a%b+diff);}


Edit: Meh, nevermind this. It doesn't work. [sad]
xmllmx
xmllmx
In other word, only these operators of {+, -, *, /} can be used!
xmllmx
xmllmx
Using standard function abs() is not permitted!
Cocalus
Cocalus 
unsigned int max(unsigned int a, unsigned int b){         bool neg=((a-b)&0x80000000);         return neg*a+!neg*b;}
xmllmx
xmllmx
Operator == is also not permitted!

Actually, Operator == is a comparing operation.
Will F
Will F
Probably not what they're looking for but:

unsigned int Max(unsigned int a, unsigned int b){    std::vector<unsigned int> foo;    foo.push_back(a);    foo.push_back(b);    std::sort( foo.begin(), foo.end() );    return foo[1];}


The code could be cleaned up a bit, but it works. [wink]

EDIT: this requirement was added while I was writing it
Quote:
Any function call is not permitted ... including STL functions.

So my solution is out.
xmllmx
xmllmx
Quote:
Original post by Cocalus
unsigned int max(unsigned int a, unsigned int b){         bool neg=((a-b)&0x80000000);         return neg*a+!neg*b;}


Note:

Only these operators of {+, -, *, /} can be used, any other operator or function call is invalid!
Trapper Zoid
Trapper Zoid
Easily hacked that around == then (I didn't know that one wasn't allowed [grin]).

unsigned int Max(unsigned int a, unsigned int b){       // I'm assuming these are *natural* numbers, i.e. non-negative   unsigned int comp1 = (b / a);     // should be zero if a > b   unsigned int comp2 = (a / b);     // should be zero if b > a   return a * !comp1 + b * !comp2;}


Edit: Oh, now you say only arithmetic commands are allowed?! I'm assuming that the boolean NOT operator is disallowed too now? Sheesh [grin].
Conner McCloud
Conner McCloud 
unsigned one(unsigned i, unsigned j) {   return max(i, j);}unsigned two(unsigned i, unsigned j) {    //the type of rLong must be signed and such that all elements of unsigned can fit.      //There are ways around this, but the easiest is just to use a bigger type    //  to perform your math    auto rLong = i - j;        //sign() can be implemented any number of ways without comparisons,     //  I just don't feel like bothering.    unsigned r = sign(rLong);    //This can be unrolled to avoid the <    for(int c = 0; c < bitsInUnsigned; c++) { //har har, see what I did there!!!        r |= sign(rLong) << c;    }    //r is now equal to 0xffffffff if a < b, and 0 if a > b    return (b & r) | (a & ~r);}


*edit: Christ I'm slow...there were no replies when I started. Anyhow, I like the looks of the division method a bit more than my way, although I'm sure I'd have gotten full points despite my insistance on reliance on standard logic gates.

CM

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.