• Create Account

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

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

222 replies to this topic

### #1xmllmx  Members   -  Reputation: 128

Like
0Likes
Like

Posted 12 February 2006 - 02:06 PM

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]

### #2xmllmx  Members   -  Reputation: 128

Like
0Likes
Like

Posted 12 February 2006 - 02:09 PM

The problem is given to the interviewees by a noted game company.

### #3knowyourrole  Members   -  Reputation: 250

Like
0Likes
Like

Posted 12 February 2006 - 02:17 PM

well... I hope I dont get that in any interview =s

I'm a little stumped currently

### #4sjelkjd  Members   -  Reputation: 168

Like
0Likes
Like

Posted 12 February 2006 - 02:17 PM

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[i][j] = b;
for(unsigned int j=0;j<i;j++) foo[i][j] = a;
foo[i][i] = a;
}

return foo[a][b];
}

And since I used a lookup table, it'll be faster than any arithmetic evaluations!

### #5xmllmx  Members   -  Reputation: 128

Like
0Likes
Like

Posted 12 February 2006 - 02:27 PM

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.

### #6DaBono  Members   -  Reputation: 692

Like
0Likes
Like

Posted 12 February 2006 - 02:28 PM

Quote:
 Original post by sjelkjdint 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?

### #7crispybacon  Members   -  Reputation: 162

Like
0Likes
Like

Posted 12 February 2006 - 02:31 PM

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.

### #8DaBono  Members   -  Reputation: 692

Like
0Likes
Like

Posted 12 February 2006 - 02:31 PM

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];
}

### #9knowyourrole  Members   -  Reputation: 250

Like
0Likes
Like

Posted 12 February 2006 - 02:34 PM

^^ I'd guess that using sort is cheating

### #10xmllmx  Members   -  Reputation: 128

Like
0Likes
Like

Posted 12 February 2006 - 02:36 PM

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.

### #11Trapper Zoid  Crossbones+   -  Reputation: 1362

Like
0Likes
Like

Posted 12 February 2006 - 02:40 PM

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...

### #12nilkn  Members   -  Reputation: 960

Like
0Likes
Like

Posted 12 February 2006 - 02:40 PM

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]

### #13xmllmx  Members   -  Reputation: 128

Like
0Likes
Like

Posted 12 February 2006 - 02:40 PM

In other word, only these operators of {+, -, *, /} can be used!

### #14xmllmx  Members   -  Reputation: 128

Like
0Likes
Like

Posted 12 February 2006 - 02:42 PM

Using standard function abs() is not permitted!

### #15Cocalus  Members   -  Reputation: 554

Like
0Likes
Like

Posted 12 February 2006 - 02:45 PM

unsigned int max(unsigned int a, unsigned int b){
bool neg=((a-b)&0x80000000);
return neg*a+!neg*b;
}

### #16xmllmx  Members   -  Reputation: 128

Like
0Likes
Like

Posted 12 February 2006 - 02:45 PM

Operator == is also not permitted!

Actually, Operator == is a comparing operation.

### #17Will F  Members   -  Reputation: 1069

Like
0Likes
Like

Posted 12 February 2006 - 02:46 PM

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.

### #18xmllmx  Members   -  Reputation: 128

Like
0Likes
Like

Posted 12 February 2006 - 02:47 PM

Quote:
 Original post by Cocalusunsigned 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!

### #19Trapper Zoid  Crossbones+   -  Reputation: 1362

Like
0Likes
Like

Posted 12 February 2006 - 02:49 PM

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].

### #20Conner McCloud  Members   -  Reputation: 1135

Like
0Likes
Like

Posted 12 February 2006 - 02:50 PM

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
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

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS