Skip to content

Instantly share code, notes, and snippets.

@adadesions

adadesions/EasyProblem1.cpp

Last active March 16, 2023 00:11
Show Gist options
  • Save adadesions/95aa72c00899a673f2afab14db08fa64 to your computer and use it in GitHub Desktop.
Save adadesions/95aa72c00899a673f2afab14db08fa64 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
EasyProblem1.cpp
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;
}
Raw
EasyProblem2.cpp
#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);
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 {};
}
Raw
Hardproblem1.cpp
#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;
}
Raw
Hardproblem2.cpp
#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;
}
Raw
Hardproblem3.cpp
#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;
}
Raw
Medproblem1.cpp
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;
}
Raw
Medproblem2.cpp
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;
}
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment