Author |
Topic: C question (find width and height of a rectangle g (Read 726 times) |
|
Spectre John
Guest
|
|
C question (find width and height of a rectangle g
« on: Jan 13th, 2005, 8:55pm » |
Quote Modify
Remove
|
Given area of a rectangle, write an efficient C code that find the 'best' rectangle for the area. The 'best' rectangle is defined as the rectangle where the difference between its width and height is the smallest between all other possible rectangles (area, width, and height are all integers). For example, if area = 24, the 'best' width and height would be 4 and 6 and not 2 and 12 or 1 and 26.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: C question (find width and height of a rectang
« Reply #1 on: Jan 13th, 2005, 10:46pm » |
Quote Modify
|
Interesting! Note that if you can give an efficient algorithm for that, you will break the RSA public key encryption.
|
|
IP Logged |
|
|
|
Spectre John
Guest
|
|
Re: C question (find width and height of a rectang
« Reply #2 on: Jan 13th, 2005, 10:47pm » |
Quote Modify
Remove
|
Really? I was aked this question during interview once, and it really stumped me...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: C question (find width and height of a rectang
« Reply #3 on: Jan 13th, 2005, 11:33pm » |
Quote Modify
|
One simple solution would start at the squareroot of the area, and then work upwords (or downwards) untill you have a length that divides the area. You could also try to find factors of the area, but using those appropriatley will definitely take more programming time.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: C question (find width and height of a rectang
« Reply #4 on: Jan 21st, 2005, 8:06pm » |
Quote Modify
|
towr's idea reminds me of this thread. Maybe something there is applicable to this one? Namely to use the built-in sqrt() function and work from there
|
|
IP Logged |
x = (0x2B | ~0x2B) x == the_question
|
|
|
|