Solved all exercises from Sem06 sem06-solutions

6 files changed, 194 insertions, 0 deletions

diff --git a/Sem. 06/Solutions/exercise01.cpp b/Sem. 06/Solutions/exercise01.cpp
new file mode 100644
index 0000000..50d2fe0
--- /dev/null
+++ b/Sem. 06/Solutions/exercise01.cpp
@@ -0,0 +1,17 @@
+#include <iostream>
+
+using namespace std;
+
+bool isPalindromeArray(int nums[], int len) {
+	for (int i = 0; i < len / 2; i++) {
+		if (nums[i] != nums[len - 1 - i])
+			return false;
+	}
+	return true;
+}
+
+int main() {
+	int numbers[5] = { 1, 2, 3, 2, 1 };
+
+	cout << isPalindromeArray(numbers, 5) << endl;
+}
diff --git a/Sem. 06/Solutions/exercise02.cpp b/Sem. 06/Solutions/exercise02.cpp
new file mode 100644
index 0000000..85572b5
--- /dev/null
+++ b/Sem. 06/Solutions/exercise02.cpp
@@ -0,0 +1,37 @@
+#include <iostream>
+
+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;
+}
diff --git a/Sem. 06/Solutions/exercise03.cpp b/Sem. 06/Solutions/exercise03.cpp
new file mode 100644
index 0000000..30b373b
--- /dev/null
+++ b/Sem. 06/Solutions/exercise03.cpp
@@ -0,0 +1,31 @@
+#include <iostream>
+
+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;
+}
+
+int gcdArray(int nums[], int len) {
+	if (len == 1) return nums[0];
+
+	int res = gcd(nums[len - 2], nums[len - 1]);
+
+	for (int i = len - 3; i >= 0; i--)
+		res = gcd(nums[i], res);
+
+	return res;
+}
+
+int main() {
+	int numbers[4] = { 9, 18, 6, 12 };
+
+	cout << gcdArray(numbers, 4) << endl;
+}
diff --git a/Sem. 06/Solutions/exercise04.cpp b/Sem. 06/Solutions/exercise04.cpp
new file mode 100644
index 0000000..fa31c84
--- /dev/null
+++ b/Sem. 06/Solutions/exercise04.cpp
@@ -0,0 +1,31 @@
+#include <iostream>
+
+using namespace std;
+
+bool isPalindromeArray(int nums[], int len, int start) {
+	int end = (len - start) / 2;
+
+	for (int i = start; i < end; i++) {
+		if (nums[i] != nums[len - 1 - i])
+			return false;
+	}
+
+	return true;
+}
+
+int isConcatOfTwoPalindromes(int nums[], int len) {
+	int border = len / 2 + 1;
+
+	return isPalindromeArray(nums, border, 0) && isPalindromeArray(nums, len, border);
+}
+
+int main() {
+	int numbers1[9] = { 1, 2, 3, 2, 1, 4, 5, 5, 4 };
+	cout << isConcatOfTwoPalindromes(numbers1, 9) << endl;
+
+	int numbers2[5] = { 1, 2, 3, 4, 5 };
+	cout << isConcatOfTwoPalindromes(numbers2, 5) << endl;
+
+	int numbers3[5] = { 1, 2, 3, 2, 1 };
+	cout << isConcatOfTwoPalindromes(numbers3, 5) << endl;
+}
diff --git a/Sem. 06/Solutions/exercise05.cpp b/Sem. 06/Solutions/exercise05.cpp
new file mode 100644
index 0000000..17eb52b
--- /dev/null
+++ b/Sem. 06/Solutions/exercise05.cpp
@@ -0,0 +1,29 @@
+#include <iostream>
+
+using namespace std;
+
+int inversionsCount(int nums[], int len) {
+	int count = 0;
+
+	for (int i = 0; i <= len - 2; i++) {
+		for (int j = i + 1; j <= len - 1; j++) {
+			if (nums[i] > nums[j])
+				count++;
+		}
+	}
+
+	return count;
+}
+
+int main() {
+	const int MAX_N = 1000;
+
+	int n;
+	cin >> n;
+
+	int nums[MAX_N] = { 0 };
+	for (int i = 0; i < n; i++)
+		cin >> nums[i];
+
+	cout << inversionsCount(nums, n) << endl;
+}
diff --git a/Sem. 06/Solutions/exercise06.cpp b/Sem. 06/Solutions/exercise06.cpp
new file mode 100644
index 0000000..6c52db3
--- /dev/null
+++ b/Sem. 06/Solutions/exercise06.cpp
@@ -0,0 +1,49 @@
+#include <iostream>
+
+using namespace std;
+
+int smallestRemovedNumber(int nums[], int len) { // Works only for non-negative numbers
+	int pivot = len / 2, diff = 0, smallest = -1, biggest = 0;
+
+	while (pivot > 0) {
+		// Pivot going to the left
+		if (nums[pivot - 1] + 1 != nums[pivot])
+			smallest = nums[pivot] - 1;
+
+		// Pivot going to the right
+		if (nums[pivot + diff] + 1 != nums[pivot + diff + 1])
+			biggest = nums[pivot + diff] + 1;
+
+		diff += 2 + (pivot % 2);
+		pivot /= 2;
+	}
+
+	return (smallest == -1) ? biggest : smallest;
+}
+
+int biggestRemovedNumber(int nums[], int len) { // Works only for non-negative numbers
+	int pivot = len / 2, diff = 0, smallest = 0, biggest = -1;
+
+	while (pivot > 0) {
+		// Pivot going to the left
+		if (nums[pivot - 1] + 1 != nums[pivot])
+			smallest = nums[pivot] - 1;
+
+		// Pivot going to the right
+		if (nums[pivot + diff] + 1 != nums[pivot + diff + 1])
+			biggest = nums[pivot + diff] + 1;
+
+		diff += 2 + (pivot % 2);
+		pivot /= 2;
+	}
+
+	return (biggest == -1) ? smallest : biggest;
+}
+
+int main() {
+	int numbers1[7] = { 5, 6, 7, 9, 10, 12, 13 };
+	cout << smallestRemovedNumber(numbers1, 7) << " " << biggestRemovedNumber(numbers1, 7) << endl;
+
+	int numbers2[5] = { 10, 12, 13, 14, 16 };
+	cout << smallestRemovedNumber(numbers2, 5) << " " << biggestRemovedNumber(numbers2, 5) << endl;
+}