1 stable release
1.0.0 | Nov 12, 2021 |
---|---|
0.5.0 |
|
0.4.1 |
|
0.3.0 |
|
0.1.9 |
|
#1842 in Algorithms
26 downloads per month
5KB
What it does
Finds a pair in a list that has the closest sum to a given number. The list can be an Array or Vector. The code is simple and free of recursion.
It expects a sorted list. Time complexity O(N)
. Space complexity O(1)
.
Features
-
Multiple types are supported, including floating points. But
usize
,u64
,u128
,i64
,i128
andf64
are not supported due to f64 cannot exactly capture these values, which is relevant in this context because various types are attemped to be converted intof64
as a general type in this crate.All other types are supported, eg.
i8
,u8
,i16
,u16
,i32
,u32
andf32
.So, if your variable type is
u64
ori64
, you should cast them tou32
andi32
respectively before passing it to the function. -
Expressive and clean code.
version note: remove unnecessary bloat and improved performance.
How to use
This crate exports a function called find_pair
that expects a reference to a sorted list (can be vector or array),and your desired sum (The sum you are looking for).
If there is no exact match, it will return the closest sum possible.
Please make sure to sort your list before passing it as an argument to the function.
Quick Start
use closest_sum_pair::interface::find_pair;
fn main() {
let mut list = [-2, -4, -7, -2, -5, -13, -7];
list.sort();
let desired_sum = -1;
let pair = find_pair(&list, desired_sum);
println!("pair {:?}", pair) // (-2, -2)
}
Example with floating point:
use closest_sum_pair::interface::find_pair;
fn main() {
let mut list: [f32; 7] =
[-2.2, -4.0, -7.9, -2.1, -5.5, -13.0, -7.1];
list.sort_by(|a, b| a.partial_cmp(b).unwrap());
let desired_sum = -16.7;
let pair = find_pair(&list, desired_sum);
println!("pair {:?}", pair) // (-13.0, -4.0)
}