Author |
Topic: A small challenge (Read 1759 times) |
|
dante
Newbie
Posts: 34
|
 |
A small challenge
« on: Jun 16th, 2007, 10:19am » |
 Quote  Modify
|
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
|
| « Last Edit: Jun 16th, 2007, 10:35am by dante » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: A small challenge
« Reply #1 on: Jun 16th, 2007, 10:26am » |
Quote Modify
|
Do we still have if and parenthesis?
given a,b,c
| hidden: |
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);
|
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dante
Newbie
Posts: 34
|
|
Re: A small challenge
« Reply #2 on: Jun 16th, 2007, 10:30am » |
Quote Modify
|
No no if else ...and they are not 3 numbers they are 3 integers ...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A small challenge
« Reply #3 on: Jun 17th, 2007, 7:17am » |
Quote Modify
|
Hmm, no if, that makes it slightly trickier.
But as long as we can still use parenthesis (or have a dependable evaluation order).
(((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)))
Hmm, that's a bit of an eyesore; maybe it can be improved to something more elegant.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: A small challenge
« Reply #4 on: Jun 17th, 2007, 10:57pm » |
Quote Modify
|
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));
} |
|
|
| « Last Edit: Jun 17th, 2007, 10:57pm by A » |
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A small challenge
« Reply #5 on: Jun 18th, 2007, 12:55am » |
Quote Modify
|
on Jun 17th, 2007, 10:57pm, R0B1N wrote: Code:
return x - ((x - y) & -(x < y));
|
|
|
|
Is that a typo, or did you mean to use a comparison operator?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
andyv
Newbie
Posts: 14
|
|
Re: A small challenge
« Reply #6 on: Jun 18th, 2007, 8:51am » |
Quote Modify
|
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;
|
| « Last Edit: Jun 18th, 2007, 10:17am by andyv » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A small challenge
« Reply #7 on: Jun 18th, 2007, 9:26am » |
Quote Modify
|
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 Jun 16th, 2007, 10:19am, dante wrote:
|
| « Last Edit: Jun 18th, 2007, 9:50am by Grimbal » |
IP Logged |
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: A small challenge
« Reply #8 on: Jun 18th, 2007, 9:38am » |
Quote Modify
|
on Jun 18th, 2007, 12:55am, 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 !!
|
|
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
arunrambo2000
Newbie
Posts: 21
|
|
Re: A small challenge
« Reply #9 on: Jun 18th, 2007, 10:00am » |
Quote Modify
|
ternary operator allowed 
|
|
IP Logged |
|
|
|
dante
Newbie
Posts: 34
|
|
Re: A small challenge
« Reply #10 on: Jun 18th, 2007, 11:48pm » |
Quote Modify
|
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
|
| « Last Edit: Jun 18th, 2007, 11:51pm by dante » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A small challenge
« Reply #11 on: Jun 19th, 2007, 12:22am » |
Quote Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dante
Newbie
Posts: 34
|
|
Re: A small challenge
« Reply #12 on: Jun 19th, 2007, 1:03am » |
Quote Modify
|
maximum integer... Among -5 -3 -2 , -2 should be the answer
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A small challenge
« Reply #13 on: Jun 19th, 2007, 1:22am » |
Quote Modify
|
how about
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)) )
nevermind.. Needs some more work..
|
| « Last Edit: Jun 19th, 2007, 1:26am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: A small challenge
« Reply #14 on: Jun 19th, 2007, 1:35am » |
Quote Modify
|
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?)
|
|
IP Logged |
|
|
|
andyv
Newbie
Posts: 14
|
|
Re: A small challenge
« Reply #15 on: Jun 19th, 2007, 1:38am » |
Quote Modify
|
dante
My solution also works with negative numbers (try it!)
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A small challenge
« Reply #16 on: Jun 19th, 2007, 1:38am » |
Quote Modify
|
And should it work for the whole range of integers?
|
|
IP Logged |
|
|
|
dante
Newbie
Posts: 34
|
|
Re: A small challenge
« Reply #17 on: Jun 19th, 2007, 2:11am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
andyv
Newbie
Posts: 14
|
|
Re: A small challenge
« Reply #18 on: Jun 19th, 2007, 3:07am » |
Quote Modify
|
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
|
| « Last Edit: Jun 19th, 2007, 3:14am by andyv » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A small challenge
« Reply #19 on: Jun 19th, 2007, 4:49am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: A small challenge
« Reply #20 on: Jun 19th, 2007, 9:31am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
andyv
Newbie
Posts: 14
|
|
Re: A small challenge
« Reply #21 on: Jun 19th, 2007, 12:31pm » |
Quote Modify
|
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;
|
| « Last Edit: Jun 19th, 2007, 12:31pm by andyv » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: A small challenge
« Reply #22 on: Jun 19th, 2007, 12:40pm » |
Quote Modify
|
Do you handle the cases when division by zero occurs, if at all?
|
| « Last Edit: Jun 19th, 2007, 12:42pm by Aryabhatta » |
IP Logged |
|
|
|
andyv
Newbie
Posts: 14
|
|
Re: A small challenge
« Reply #23 on: Jun 19th, 2007, 12:46pm » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
andyv
Newbie
Posts: 14
|
|
Re: A small challenge
« Reply #24 on: Jun 19th, 2007, 1:04pm » |
Quote Modify
|
on Jun 19th, 2007, 9:31am, 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;
|
| « Last Edit: Jun 19th, 2007, 1:10pm by andyv » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print