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}