DEV Community

loading...

Challenge: Get Closest Number in an Array

andy profile image Andy Zhao (he/him) ・1 min read

Given an array of numbers nums, and a given number given_num:

nums = [100, 200, 400, 800, 1600, 3200, 6400, 128000]
given_num = 900
Enter fullscreen mode Exit fullscreen mode

Get the number closest to the given_num from the array nums.

In this example, the returned value should be 800.

Go!

A black checkered flag signals go!

Discussion

pic
Editor guide
Collapse
link2twenty profile image
Andrew Bone

Javascript:

Let's go for a JS one liner 😉

nums.sort((a, b) => Math.abs(given_num - a) - Math.abs(given_num - b))[0]

This causes the original array to have its order changed but I don't think that's against the rules 😅

Collapse
bugb profile image
bugb

I dont think use sort is good idea:
Let see:

[2,3,4,11].sort()
Collapse
link2twenty profile image
Andrew Bone

By including a function to sort by I'm no longer doing an alphabetical sort, which means this problem no longer exists.

  console.log([2,3,4,11].sort((a,b)=>a-b));
Output:
  (4) [2, 3, 4, 11]

The sort() method sorts the elements of an array in place and returns the array. The default sort order is built upon converting the elements into strings, then comparing their sequences of UTF-16 code units values.

developer.mozilla.org/en-US/docs/W...

Thread Thread
bugb profile image
bugb

yes, by including compareFunction callback, we can solve this problem.

Collapse
andy profile image
Andy Zhao (he/him) Author

If it outputs the closest number, it works! :)

Collapse
dmfay profile image
Dian Fay

Window functions!

SELECT unnest
FROM unnest(ARRAY[100,200,400,800,1600,3200,6400,128000])
ORDER BY row_number() OVER (ORDER BY abs(900 - unnest))
LIMIT 1;
Collapse
rhymes profile image
rhymes

hahaha thinking outside the box :D

Collapse
dmfay profile image
Dian Fay

I looked at it again just now and the row_number is redundant anyway...

SELECT unnest
FROM unnest(ARRAY[100,200,400,800,1600,3200,6400,128000])
ORDER BY abs(900 - unnest)
LIMIT 1;
Collapse
joelnet profile image
JavaScript Joel

This is a job for Reduce!

JavaScript:

const nums = [100, 200, 400, 800, 1600, 3200, 6400, 128000]
const given_num = 900

const closestReducer = g => (a, b) =>
  Math.abs(g - a) < Math.abs(g - b) ? a : b

nums.reduce(closestReducer(given_num))
//=> 800
Collapse
andy profile image
Andy Zhao (he/him) Author

Ruby:

nums.min_by { |num| (given_num - num).abs }
#=> 800

Shamelessly taken from Stack Overflow 🙃 I was in a much more of a "just give me the answer" mood than "let's figure it out" mood.

Collapse
hpj1992 profile image
Harshit

Java:

        int[] nums = {100, 200, 400, 800, 1600, 3200, 6400, 128000};
        int ans = 0;
        int given_num = 900;
        int minDistance = Integer.MAX_VALUE;
        for (int i =0; i < nums.length; i++) {
            int curDistance = Math.abs(nums[i] - given_num);
            if (curDistance < minDistance) {
                ans = nums[i];
                minDistance = curDistance;
            }
        }
        System.out.println(ans);

Trying to optimize no of lines with Java 8 Streams and Lambda.

Collapse
pbouillon profile image
Pierre Bouillon

Here goes Python !

min(nums, key=lambda x: abs(x - given_num))
Collapse
lucifer1004 profile image
Gabriel Wu

Using JavaScript Set:

const closest_num = (nums, given_num) => {
  const min_dist = Math.min(...nums.map(num => Math.abs(num - given_num)))
  return new Set(nums).has(given_num - min_dist) ? given_num - min_dist : given_num + min_dist
}
Collapse
lucifer1004 profile image
Gabriel Wu

Or we can save the intermediate array:

const closest_num = (nums, given_num) => {
  const absolute_dists = nums.map(num => Math.abs(num - given_num))
  const min_absolute_dist = Math.min(...absolute_dists)
  return nums[absolute_dists.indexOf(min_absolute_dist)]
}
Collapse
jarvism101 profile image
Aamir Nazir

A Python implementation:

import numpy as np
def find_nearest(array, value):
    array = np.asarray(array)
    idx = (np.abs(array - value)).argmin()
    return array[idx]

nums = [100, 200, 400, 800, 1600, 3200, 6400, 128000]
given_num = 900

print(find_nearest(nums, given_num))
Collapse
lucifer1004 profile image
Gabriel Wu

And there is another perspective, instead of iterating numbers, we can iterate distances. Like:

const closest_num = (nums, given_num) => {
  const set = new Set(nums)
  let i = 0
  while (true) {
    if (set.has(given_num - i)) return given_num - i
    if (set.has(given_num + i)) return given_num + i
    i++
  }
}

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:

const benchmark = (func) => {
  console.time(func.name)
  func.call(this, Array.from({length: 10000000}, (v, idx) => (10000000 - idx)), 10000001)
  console.timeEnd(func.name)
}

You can test your function via benchmark(func).

The solution above yields:

closest_num: 5037.456787109375ms

in Chrome.

Collapse
jamesmh profile image
James Hickey

Here's some C# for everyone:

var nums = new int[] { 100, 200, 400, 800, 1600, 3200, 6400, 128000 };
var given_num = 900;

var result = 
    (
        from num in nums
        let diff = Math.Abs(given_num - num)
        orderby diff
        select num
    )
    .First();
Collapse
detunized profile image
Dmitry Yakimenko

C++, O(n), no sorting, no extra memory allocation beyond storing the input:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v{100, 200, 400, 800, 1600, 3200, 6400, 128000};
    int given_num = 900;

    cout << *min_element(
        v.begin(), 
        v.end(), 
        [=](int a, int b){ return abs(a - given_num) < abs(b - given_num); }
    );

    return 0;
}
Collapse
mkrl profile image
Mikhail Korolev

Wolfram Language!

Nearest[nums, given_num]

I knew that one day my subscription will come in handy...

Collapse
n13 profile image
Nik

Swift is the most elegant concise and bestest language... ;)

nums.reduce(nums[0]) { abs($0-given_num) < abs($1-given_num) ? $0 : $1 } 

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)

extension CGFloat {    
    func nearest(arr: [CGFloat]) -> CGFloat {
        guard arr.count > 0 else {
            fatalError("array cannot be empty")
        }
        return arr.reduce(arr[0]) { abs($0-self) < abs($1-self) ? $0 : $1 } 
    }
}

let nums: [CGFloat] = [100, 200, 400, 800, 1600, 3200, 6400, 128000] 
let given_num = CGFloat(900)

let nearest = given_num.nearest(nums)

Collapse
kennethlum profile image
Kenneth Lum

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)

Collapse
bugb profile image
bugb

nums = [100, 200, 400, 800, 1600, 3200, 6400, 128000];
given_num = 900

Here is my solution:

f = a => (m=Math.min(...nums.map(v=>Math.abs(v-given_num))),nums.find(v=>v==given_num - m || v== m-given_num))

Usage:

f(nums)

Result:

800
Collapse
lucifer1004 profile image
Gabriel Wu

Be careful that ... can cause a range error:

RangeError: Maximum call stack size exceeded

when the nums array is very large.

Collapse
highcenburg profile image
Vicente G. Reyes

With the help of google, I was able to find the answer to this 😅

import numpy as np
def find_nearest(array, value):
array = np.array(array)
z=np.abs(array-value)
y= np.where(z == z.min())
m=np.array(y)
x=m[0,0]
y=m[1,0]
near_value=array[x,y]

return near_value

array =np.array([[100, 200, 400, 800, 1600, 3200, 6400, 128000]])
print(array)
value = 900
print(find_nearest(array, value))

Answer:

Thanks for this challenge! 🍺

Collapse
vorsprung profile image
vorsprung
package main


import (
        "fmt"
        "sort"
)

func main() {
        l := []int{100, 200, 400, 800, 901, 1600, 3200, 6400, 128000}
        target := 900
        n := sort.SearchInts(l, target)
        if l[n]-target < target-l[n-1] {
                n += 1
        }
        fmt.Printf("%d\n", l[n-1])
}

play.golang.org/p/xxzN4y-fPF0

Collapse
fakirsayoub profile image
Ayoub Fakir

Hey! Let's do it the Scala way:

def closestNumber(x: Int, y: Int, givenNumber: Int): Int = {
    if(abs(givenNumber-x) > abs(givenNumber-y)) {
        y
    } else {
        x
    }
}

val givenNumber = 900
val nums = List(100, 200, 400, 800, 1600, 3200, 6400, 128000)
println(nums.reduce((x, y) => closestNumber(x, y, givenNumber)))
//==> Prints 800

Thanks for the challenge!

Collapse
modaf profile image
Modaf

OCaml with list instead of array

let rec closest num list = match list with
[] -> failwith "Empty list"
|[n] -> n
|h :: q ->
    let closest_q = closest num q in
    let val_h = abs (num - h) in
    let val_q = abs (num - closest_q) in
    if (val_h < val_q) then h else closest_q;;
Collapse
choroba profile image
E. Choroba

Perl solution:

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use List::AllUtils qw{ min_by };

my @nums = (100, 200, 400, 800, 1600, 3200, 6400, 128000);
my $given_num = 900;

say $nums[ min_by { abs($nums[$_] - $given_num) } 0 .. $#nums ];
Collapse
lucifer1004 profile image
Gabriel Wu

What if there are two numbers that are equally close to the given number?
I think you should point this out in the description.

Collapse
kip13 profile image
kip

Rust 🦀

numbers.iter().min_by_key(|&num| (num - given_num).abs()).unwrap()
Collapse
andy profile image
Andy Zhao (he/him) Author

Nice, didn't know Rust had similar syntax to Ruby!

Collapse
maeganwilson_ profile image
Maegan Wilson

I probably over complicated it, but here's a CodePen link with how I did it in JS and outputted it to the HTML side.

Collapse
andy profile image
Andy Zhao (he/him) Author

Long as you solved it! 👍

Collapse
lucifer1004 profile image
Gabriel Wu

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.

Collapse
vorsprung profile image
vorsprung

yeah, that's why I used a binary search library function in my answer :)

Collapse
andreyvladikin profile image
Andrey Vladikin

JS:

const nums = [100, 200, 400, 800, 1600, 3200, 6400, 128000];
const givenNum = 900;

nums
.map(n => ({n, d: Math.abs(n-givenNum)}))
.sort((n1, n2) => Math.sign(n1.d - n2.d))[0].n