ads_rs/v1/math/lcm.rs
1use crate::v1::math::gcd_many;
2
3/// Finds the LCM (Least Common Multiple) for an array of elements.
4/// # Examples
5/// ```
6/// use ads_rs::prelude::v1::math::lcm_many;
7///
8/// let res0 = lcm_many(&[42, 8, 144]);
9/// let res1 = lcm_many(&[89, 144, 233, 377, 610]);
10/// let res2 = lcm_many(&[25, 105, 235, 100]);
11///
12/// assert_eq!(24192, res0);
13/// assert_eq!(686719856160, res1);
14/// assert_eq!(12337500, res2);
15/// ```
16/// ## Corner cases
17/// - LCM of an empty array equals 0.
18/// - LCM of a single element array equals that element.
19/// ```
20/// use ads_rs::prelude::v1::math::lcm_many;
21///
22/// let res0 = lcm_many(&[]);
23/// let res1 = lcm_many(&[25]);
24///
25/// assert_eq!(0, res0);
26/// assert_eq!(25, res1);
27/// ```
28/// # Implementation details
29/// - Stein's algorithm is used to find GCD (from [`gcd_many`]).
30/// - Time complexity: O(K * N<sup>2</sup>) where:
31/// - N - bits count in the biggest number.
32/// - K - number's count
33pub fn lcm_many(elems: &[u64]) -> u64 {
34 if elems.is_empty() {
35 return 0;
36 }
37
38 if elems.len() == 1 {
39 return elems[0];
40 }
41
42 let gcd = gcd_many(elems);
43
44 // GCD is zero only when all elements are zeros
45 if gcd == 0 {
46 return 0;
47 }
48
49 elems[1..].iter().fold(elems[0] / gcd, |acc, e| acc * (*e))
50}
51
52/// Finds an LCM (Least Common Multiple) for a pair of numbers.
53/// # Examples
54/// ```
55/// use ads_rs::prelude::v1::math::lcm;
56///
57/// let res0 = lcm(42, 144);
58/// let res1 = lcm(377, 610);
59/// let res2 = lcm(105, 25);
60///
61/// assert_eq!(1008, res0);
62/// assert_eq!(229970, res1);
63/// assert_eq!(525, res2);
64/// ```
65/// ## Corner case
66/// LCM of both zero numbers equals 0.
67/// ```
68/// use ads_rs::prelude::v1::math::lcm;
69///
70/// let res = lcm(0, 0);
71///
72/// assert_eq!(0, res);
73/// ```
74/// # Implementation details
75/// - Stein's algorithm used (from [`gcd_many`]).
76/// - Time complexity: O(N<sup>2</sup>) where N - number of bits in the biggest number.
77#[inline]
78pub fn lcm(lhs: u64, rhs: u64) -> u64 {
79 lcm_many(&[lhs, rhs])
80}
81
82#[cfg(test)]
83mod tests {
84 use super::*;
85
86 #[test]
87 fn lcm_many_works() {
88 // arrange
89 let test_suits = [
90 // Empty array
91 (vec![], 0),
92 // Single element
93 (vec![223], 223),
94 // Relative prime numbers
95 (vec![1, 2, 3, 4, 5], 120),
96 // Regular case
97 (vec![8, 24, 156, 36], 269568),
98 // All zeros
99 (vec![0, 0, 0, 0], 0),
100 ];
101
102 // act
103 let result: Vec<u64> = test_suits.iter().map(|t| lcm_many(&t.0)).collect();
104
105 // assert
106 for i in 0..test_suits.len() {
107 assert_eq!(test_suits[i].1, result[i]);
108 }
109 }
110}