wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> A small challenge
        
(Message started by: dante on Jun 16th, 2007, 10:19am)
Title: A small challenge
Post by dante on Jun 16th, 2007, 10:19am
Donno whether its here already...
Write a C program to find the biggest of 3 integers using only +,-,*,/.
No if else ,no functions, no loops,no switch cases ..etc ...only there can be main function and functions for getting input and printing output.. the processing can include = for assignment to variables
Title: Re: A small challenge
Post by towr on Jun 16th, 2007, 10:26am
Do we still have if and parenthesis?

given a,b,c

[hideb]
if((a/b) * (a/c)) // a is largest
 print(a);
elseif (b/c) // a isn't the largest, so the largest of b and c is
 print(b);
else
 print(c);
[/hideb]
Title: Re: A small challenge
Post by dante on Jun 16th, 2007, 10:30am
No no if else ...and they are not 3 numbers they are 3 integers ...
Title: Re: A small challenge
Post by towr on Jun 17th, 2007, 7:17am
Hmm, no if, that makes it slightly trickier.
But as long as we can still use parenthesis (or have a dependable evaluation order).

[hide](((a/b) * (a/c)) * a + ((b/a) * (b/c)) * b + ((c/a) * (c/b)) * c) / ( ((a/b) * (a/c)) + ((b/a) * (b/c)) + ((c/a) * (c/b)))[/hide]

Hmm, that's a bit of an eyesore; maybe it can be improved to something more elegant.
Title: Re: A small challenge
Post by R0B1N on Jun 17th, 2007, 10:57pm
Therz one Solution Using Only Bitwise operators , used to find largest of 2 integers . One can use the same to Find largest of 3 numbers as well

Say

Code:
int Max ( int a , int b , int c )
{
     return Max ( Max(a,b),c);
}


Of course , to avoid new functions you can unwrap the code  :)


Code:
int Max ( int x , int y )
{
   return x - ((x - y) & -(x < y));
}
Title: Re: A small challenge
Post by towr on Jun 18th, 2007, 12:55am

on 06/17/07 at 22:57:26, R0B1N wrote:

Code:
   return x - ((x - y) & -(x < y));
Is that a typo, or did you mean to use a comparison operator?
Title: Re: A small challenge
Post by andyv on Jun 18th, 2007, 8:51am
     int a, b, c;
     std::cin >> a >> b >> c;
     int maxab = a + (b - a) * ( (a - b) / 0x80000000 );
     int maxabc = c + (maxab - c) * ( (c - maxab) / 0x80000000 );
     std::cout << maxabc;
Title: Re: A small challenge
Post by Grimbal on Jun 18th, 2007, 9:26am
max = ~(i-j|i-k)>>31&i | ~(j-k|j-i)>>31&j | ~(k-i|k-j)>>31&k;

works only for numbers from -2^30 to 2^30-1

Oops:

on 06/16/07 at 10:19:11, dante wrote:
... using only +,-,*,/.
Title: Re: A small challenge
Post by R0B1N on Jun 18th, 2007, 9:38am

on 06/18/07 at 00:55:31, towr wrote:
Is that a typo, or did you mean to use a comparison operator?



>:(  :-[  :-[

Errrrr .... I Should read question More carefully ,Anyways thats the method i know when the question is to do it Without Any Branching !!
Title: Re: A small challenge
Post by arunrambo2000 on Jun 18th, 2007, 10:00am
ternary operator allowed ???
Title: Re: A small challenge
Post by dante on Jun 18th, 2007, 11:48pm
towr,andyv
by integers I meant the solution should include for negative numbers like -5,-3,-2 etc ....

paranthesis allowed
Grimbal
strictly there shud be no other operators other +,-,*,/

arunrambo2000,
ternary not allowed
Title: Re: A small challenge
Post by towr on Jun 19th, 2007, 12:22am
Do you want the maximum integer, or the integer with the greatest magnitude (absolute value). i.e. what sort of bigness are you looking for?
I'm fairly sure my solution works for returning the number with the greatest magnitude..
Title: Re: A small challenge
Post by dante on Jun 19th, 2007, 1:03am
maximum integer... Among -5 -3 -2 , -2 should be the answer
Title: Re: A small challenge
Post by towr on Jun 19th, 2007, 1:22am
how about
[hide]max(a,b) = (((a/b) + ((a*a)/(b*b))) * a + ((b/a) + ((b*b)/(a*a))) * b) / ((a/b) + ((a*a)/(b*b)) + (b/a) + ((b*b)/(a*a)) )[/hide]

nevermind.. Needs some more work..
Title: Re: A small challenge
Post by Aryabhatta on Jun 19th, 2007, 1:35am
Question to dante: Are you expecting something C specific or do you think we can give a solution independent of the language?

Perhaps some arithmetic expression which evaluates to the max?

Also, is there an assumption of 32 bit integers? (Or some other fixed size?)
Title: Re: A small challenge
Post by andyv on Jun 19th, 2007, 1:38am
dante
My solution also works with negative numbers (try it!)
Title: Re: A small challenge
Post by Grimbal on Jun 19th, 2007, 1:38am
And should it work for the whole range of integers?
Title: Re: A small challenge
Post by dante on Jun 19th, 2007, 2:11am
andyv
sorry ..
you got it right ... cheers ...
can you explain more about the solution .. particularly the division by 0x80000000

aryabhatta
ya its C specific ... and I expected some expression ..

Regarding range ,even if it solves -100 to 100 its great
Title: Re: A small challenge
Post by andyv on Jun 19th, 2007, 3:07am
The idea is

int maxb = a  +  expr(a, b) * ( b - a)
where expr (a, b) should 1 if b > a, 0 otherwise
So we must construct expr.

I use the fact that, internally,  the first bit of a negative number is 1. So the first idea is to cast (a - b) to "unsigned int" and then shift right 31 positions.
(unsigned int) (a - b) >> 31.
Shift right operation is not allowed, so I replace it with division to 2^31 (0x80000000). The  constant 0x80000000 is of type unsigned int. When dividing an int to an unsigned int, the int is automatically casted to unsigned int. So typecasting is no longer necessary
Title: Re: A small challenge
Post by Grimbal on Jun 19th, 2007, 4:49am
It works in the range from -2^30 to 2^30-1, which is half of the whole range of integers, a bit more than -100000000 to 1000000000.
Title: Re: A small challenge
Post by Aryabhatta on Jun 19th, 2007, 9:31am
Not to take away anything from the solutions given, honestly, this was a bit of a let-down. I was expecting something more generic with an Aha factor.  :(

Something similar to:

You are given 3 numbers a, b, c of which two are equal and the third is different. Write an arithmetic expression (using brackets, +,-, *, /) which evaluates to the non-repeated value.
Title: Re: A small challenge
Post by andyv on Jun 19th, 2007, 12:31pm
My second solution (completely independent of the internal representation of types) :
int a, b, c;
std::cin >> a >> b >> c;
int aa = a + a * a + b * b + 1;
int bb = b + a * a + b * b + 1;
int maxab = ((aa/bb) * aa + (bb/aa) * bb) / ( (aa/bb) + (bb/aa)) - a * a - b * b - 1;
int mm = maxab + maxab * maxab + c * c + 1;
int cc = c  + maxab * maxab + c * c + 1;
int maxabc = ((mm/cc) * mm + (cc/mm) * cc) / ( (mm/cc) + (cc/mm)) - maxab * maxab - c * c - 1;
std::cout << maxabc << std::endl;
Title: Re: A small challenge
Post by Aryabhatta on Jun 19th, 2007, 12:40pm
Do you handle the cases when division by zero occurs, if at all?
Title: Re: A small challenge
Post by andyv on Jun 19th, 2007, 12:46pm
That's the trick. Division by zero can no occur.
Instead of finding the maximum of a and b, I
find the maximum of
aa = a + a * a + b * b + 1 and
bb = b + a * a + b * b + 1
aa and bb are positive for sure (in the end i subtract from the  found maximum (a  * a + b * b + 1) to get the maximum of a and b)
Title: Re: A small challenge
Post by andyv on Jun 19th, 2007, 1:04pm

on 06/19/07 at 09:31:50, Aryabhatta wrote:
You are given 3 numbers a, b, c of which two are equal and the third is different. Write an arithmetic expression (using brackets, +,-, *, /) which evaluates to the non-repeated value.


int a, b, c;
std::cin >> a >> b >> c;
int x = (a * (b - a) * (c - a) + b * (a - b) * (c - b) + c * (a - c) * (b -c)) /
                ( (b - a) * (c - a) + (a - b) * (c - b) +  (a - c) * (b -c));
std::cout << x << std::endl;
Title: Re: A small challenge
Post by Aryabhatta on Jun 19th, 2007, 1:23pm

on 06/19/07 at 13:04:37, andyv wrote:
int a, b, c;
std::cin >> a >> b >> c;
int x = (a * (b - a) * (c - a) + b * (a - b) * (c - b) + c * (a - c) * (b -c)) /
                ( (b - a) * (c - a) + (a - b) * (c - b) +  (a - c) * (b -c));
std::cout << x << std::endl;


You got it! Well done.
Title: Re: A small challenge
Post by Grimbal on Jun 20th, 2007, 2:04am
What if all 3 numbers are equal?
Oops, wrong problem.
Title: Re: A small challenge
Post by SMQ on Jun 20th, 2007, 6:10am

on 06/20/07 at 02:04:02, Grimbal wrote:
What if all 3 numbers are equal?

Then it's perfectly free to divide by zero as the question stated: " You are given 3 numbers a, b, c of which two are equal and the third is different."  Outside of those conditions, behavior is undefined.

--SMQ
Title: Re: A small challenge
Post by aki_scorpion on Jul 8th, 2007, 3:36am
Hey how about this solution
For any three nos. a,b,c

temp=(a+b+abs(a-b))/2
Ans=(c+temp+abs(c-temp))/2

here temp is any temporary variable and the answer is in Ans.
Title: Re: A small challenge
Post by towr on Jul 8th, 2007, 8:21am

on 07/08/07 at 03:36:57, aki_scorpion wrote:
Hey how about this solution
For any three nos. a,b,c

temp=(a+b+abs(a-b))/2
Ans=(c+temp+abs(c-temp))/2

here temp is any temporary variable and the answer is in Ans.
Abs is not a given function; so the question is how do you implement it with only the given operators?


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board