adadesions · March 16, 2023 00:11 · Mar 16, 2023 · Mar 15, 2023 · Mar 15, 2023 · Mar 15, 2023
diff --git a/Medproblem2.cpp b/Medproblem2.cpp
@@ -17,4 +17,21 @@ bool searchMatrix(vector<vector<int>>& matrix, int target) {
             }
         }
         return false;
-    }
+    }
+
+int main () {
+        vector<vector<int>> matrix = {
+            {1, 3, 5, 7},
+            {10, 11, 16, 20},
+            {23, 30, 34, 50}
+        };
+        int target = 13;
+        bool found = searchMatrix(matrix, target);
+        if (found) {
+            cout << "Target found in matrix" << endl;
+        } else {
+            cout << "Target not found in matrix" << endl;
+        }
+
+        return 1;
+}
diff --git a/EasyProblem2.cpp b/EasyProblem2.cpp
@@ -1,3 +1,10 @@
+#include <iostream>
+#include <vector>
+#include <numeric>
+#include <algorithm>
+
+using namespace std;
+
 vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) {
     int sumAlice = accumulate(aliceSizes.begin(), aliceSizes.end(), 0);
     int sumBob = accumulate(bobSizes.begin(), bobSizes.end(), 0);

diff --git a/EasyProblem1.cpp b/EasyProblem1.cpp
@@ -0,0 +1,18 @@
+bool isPerfectSquare(int num) {
+    if (num < 2) {
+        return true;
+    }
+    int left = 2, right = num / 2;
+    while (left <= right) {
+        long long mid = left + (right - left) / 2;
+        long long square = mid * mid;
+        if (square == num) {
+            return true;
+        } else if (square > num) {
+            right = mid - 1;
+        } else {
+            left = mid + 1;
+        }
+    }
+    return false;
+}
diff --git a/EasyProblem2.cpp b/EasyProblem2.cpp
@@ -0,0 +1,12 @@
+vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) {
+    int sumAlice = accumulate(aliceSizes.begin(), aliceSizes.end(), 0);
+    int sumBob = accumulate(bobSizes.begin(), bobSizes.end(), 0);
+    unordered_set<int> setBob(bobSizes.begin(), bobSizes.end());
+    int diff = (sumAlice - sumBob) / 2;
+    for (int candy : aliceSizes) {
+        if (setBob.count(candy - diff)) {
+            return {candy, candy - diff};
+        }
+    }
+    return {};
+}
diff --git a/problem3.cpp → Hardproblem1.cpp b/problem3.cpp → Hardproblem1.cpp
diff --git a/problem4.cpp → Hardproblem2.cpp b/problem4.cpp → Hardproblem2.cpp
diff --git a/problem5.cpp → Hardproblem3.cpp b/problem5.cpp → Hardproblem3.cpp
diff --git a/problem1.cpp → Medproblem1.cpp b/problem1.cpp → Medproblem1.cpp
diff --git a/problem2.cpp → Medproblem2.cpp b/problem2.cpp → Medproblem2.cpp
diff --git a/problem1.cpp b/problem1.cpp
@@ -0,0 +1,17 @@
+int search(vector<int>& nums, int target) {
+    int left = 0;
+    int right = nums.size() - 1;
+
+    while (left <= right) {
+        int mid = left + (right - left) / 2;
+        if (nums[mid] == target) {
+            return mid;
+        } else if (nums[mid] < target) {
+            left = mid + 1;
+        } else {
+            right = mid - 1;
+        }
+    }
+
+    return -1;
+}
diff --git a/problem2.cpp b/problem2.cpp
@@ -0,0 +1,20 @@
+bool searchMatrix(vector<vector<int>>& matrix, int target) {
+        int m = matrix.size();
+        if (m == 0) return false;
+        int n = matrix[0].size();
+        if (n == 0) return false;
+
+        int left = 0, right = m * n - 1;
+        while (left <= right) {
+            int mid = (left + right) / 2;
+            int row = mid / n, col = mid % n;
+            if (matrix[row][col] == target) {
+                return true;
+            } else if (matrix[row][col] < target) {
+                left = mid + 1;
+            } else {
+                right = mid - 1;
+            }
+        }
+        return false;
+    }
diff --git a/problem3.cpp b/problem3.cpp
@@ -0,0 +1,62 @@
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
+    int m = nums1.size();
+    int n = nums2.size();
+    // ensure that nums1 is the smaller array
+    if (m > n) {
+        return findMedianSortedArrays(nums2, nums1);
+    }
+    int left = 0;
+    int right = m;
+    int half_len = (m + n + 1) / 2;
+    while (left <= right) {
+        int i = left + (right - left) / 2;
+        int j = half_len - i;
+        if (i < right && nums2[j-1] > nums1[i]) {
+            // i is too small, increase it
+            left = i + 1;
+        } else if (i > left && nums1[i-1] > nums2[j]) {
+            // i is too big, decrease it
+            right = i - 1;
+        } else {
+            // i is perfect, calculate the median
+            int max_left = 0;
+            if (i == 0) {
+                max_left = nums2[j-1];
+            } else if (j == 0) {
+                max_left = nums1[i-1];
+            } else {
+                max_left = max(nums1[i-1], nums2[j-1]);
+            }
+            if ((m + n) % 2 == 1) {
+                return max_left;
+            }
+            int min_right = 0;
+            if (i == m) {
+                min_right = nums2[j];
+            } else if (j == n) {
+                min_right = nums1[i];
+            } else {
+                min_right = min(nums1[i], nums2[j]);
+            }
+            return (max_left + min_right) / 2.0;
+        }
+    }
+    return 0.0;
+}
+
+int main() {
+    vector<int> nums1 = {1, 3};
+    vector<int> nums2 = {2};
+    cout << findMedianSortedArrays(nums1, nums2) << endl; // Output: 2.00000
+
+    nums1 = {1, 2};
+    nums2 = {3, 4};
+    cout << findMedianSortedArrays(nums1, nums2) << endl; // Output: 2.50000
+
+    return 0;
+}
diff --git a/problem4.cpp b/problem4.cpp
@@ -0,0 +1,37 @@
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+int findMin(vector<int>& nums) {
+    int left = 0;
+    int right = nums.size() - 1;
+    while (left < right) {
+        int mid = left + (right - left) / 2;
+        if (nums[mid] > nums[right]) {
+            // right half is sorted, search in left half
+            left = mid + 1;
+        } else if (nums[mid] < nums[left]) {
+            // left half is sorted, search in right half
+            right = mid;
+        } else {
+            // can't determine which half is sorted, perform linear search
+            int min_val = nums[left];
+            for (int i = left + 1; i <= right; i++) {
+                min_val = min(min_val, nums[i]);
+            }
+            return min_val;
+        }
+    }
+    return nums[left];
+}
+
+int main() {
+    vector<int> nums1 = {1, 3, 5};
+    cout << findMin(nums1) << endl; // Output: 1
+
+    vector<int> nums2 = {2, 2, 2, 0, 1};
+    cout << findMin(nums2) << endl; // Output: 0
+
+    return 0;
+}
diff --git a/problem5.cpp b/problem5.cpp
@@ -0,0 +1,50 @@
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+bool is_valid_split(vector<int>& nums, int k, int max_sum) {
+    int count = 1;
+    int sum = 0;
+    for (int num : nums) {
+        sum += num;
+        if (sum > max_sum) {
+            count++;
+            sum = num;
+        }
+        if (count > k) {
+            return false;
+        }
+    }
+    return true;
+}
+
+int splitArray(vector<int>& nums, int k) {
+    int left = 0;
+    int right = 0;
+    for (int num : nums) {
+        left = max(left, num);
+        right += num;
+    }
+    while (left < right) {
+        int mid = left + (right - left) / 2;
+        if (is_valid_split(nums, k, mid)) {
+            right = mid;
+        } else {
+            left = mid + 1;
+        }
+    }
+    return left;
+}
+
+int main() {
+    vector<int> nums1 = {7, 2, 5, 10, 8};
+    int k1 = 2;
+    cout << splitArray(nums1, k1) << endl; // Output: 18
+
+    vector<int> nums2 = {1, 2, 3, 4, 5};
+    int k2 = 2;
+    cout << splitArray(nums2, k2) << endl; // Output: 9
+
+    return 0;
+}