From d6e6b0328ce2a4fe228262713e89e391421f5ab3 Mon Sep 17 00:00:00 2001 From: Syndamia Date: Wed, 17 Nov 2021 09:26:15 +0200 Subject: Added my solutions to Sem. 06 exercises --- .../Solutions Sem. 06/exercise02.cpp | 37 ++++++++++++++++++++++ 1 file changed, 37 insertions(+) create mode 100644 Year 1/Programming introduction/Solutions Sem. 06/exercise02.cpp (limited to 'Year 1/Programming introduction/Solutions Sem. 06/exercise02.cpp') diff --git a/Year 1/Programming introduction/Solutions Sem. 06/exercise02.cpp b/Year 1/Programming introduction/Solutions Sem. 06/exercise02.cpp new file mode 100644 index 0000000..85572b5 --- /dev/null +++ b/Year 1/Programming introduction/Solutions Sem. 06/exercise02.cpp @@ -0,0 +1,37 @@ +#include + +using namespace std; + +// Greatest Common Divisor +int gcd(int a, int b) { + // Eucledian algorithm + while (b != 0) { + int temp = b; + b = a % b; + a = temp; + } + return a; +} + +// Least Common Multiple +int lcm(int a, int b) { + // https://en.wikipedia.org/wiki/Least_common_multiple#Using_the_greatest_common_divisor + return (a * b) / gcd(a, b); +} + +int lcmArray(int nums[], int len) { + if (len == 1) return nums[0]; + + int res = lcm(nums[len - 2], nums[len - 1]); + + for (int i = len - 3; i >= 0; i--) + res = lcm(nums[i], res); + + return res; +} + +int main() { + int numbers[4] = { 9, 18, 6, 12 }; + + cout << lcmArray(numbers, 4) << endl; +} -- cgit v1.3.1-26-gb76a