Given an array of numbers nums
, and a given number given_num
:
nums = [100, 200, 400, 800, 1600, 3200, 6400, 128000]
given_num = 900
Get the number closest to the given_num
from the array nums
.
In this example, the returned value should be 800
.
Latest comments (36)
It looks like the array is sorted. If it is sorted, then the following should be optimal:
Binary search for the left insertion point, and then for the right insertion point.
If found, then that's the answer.
Otherwise, check the left or right number and see which one is closer to the
target
.Time complexity: O(log n)
Swift is the most elegant concise and bestest language... ;)
Of course in actual usage we would make this an extension and check the validity of the array. I came across this post because I needed it so this one's for CGFloat, which is a Swift floating point type (Double, really)
Perl solution:
A Python implementation:
If the given array is ascending/descending, then the task becomes a binary search.
The pleasure of programming lies in that even those things appearing to be very simple are also worth thinking.
yeah, that's why I used a binary search library function in my answer :)
And there is another perspective, instead of iterating numbers, we can iterate distances. Like:
This will normally be slower, but in cases like:
nums = [10000000, 9999999, 9999998, ..., 1]
given_num = 10000001
It will be much faster than other algorithms.
I have written a benchmark function for this:
You can test your function via
benchmark(func)
.The solution above yields:
closest_num: 5037.456787109375ms
in Chrome.
Using JavaScript
Set
:Or we can save the intermediate array:
What if there are two numbers that are equally close to the given number?
I think you should point this out in the description.
Hey! Let's do it the Scala way:
Thanks for the challenge!
play.golang.org/p/xxzN4y-fPF0
Here's some C# for everyone:
OCaml with list instead of array
C++, O(n), no sorting, no extra memory allocation beyond storing the input:
nums = [100, 200, 400, 800, 1600, 3200, 6400, 128000];
given_num = 900
Here is my solution:
Usage:
Result:
Be careful that
...
can cause a range error:RangeError: Maximum call stack size exceeded
when the
nums
array is very large.Javascript:
Let's go for a JS one liner 😉
This causes the original array to have its order changed but I don't think that's against the rules 😅
If it outputs the closest number, it works! :)
I dont think use
sort
is good idea:Let see:
By including a function to sort by I'm no longer doing an alphabetical sort, which means this problem no longer exists.
developer.mozilla.org/en-US/docs/W...
yes, by including compareFunction callback, we can solve this problem.