Welcome to Day 14 of the 100 Days of DSA challenge! Today’s focus was on exploring advanced searching techniques, particularly extending Binary Search to solve intricate optimization problems. These tasks demonstrated the adaptability of Binary Search and its potential to tackle complex scenarios efficiently.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s dive into the challenges tackled today! 🚀✨
1. Allocate Minimum Number of Pages
This program allocates books to students such that the maximum pages assigned to any student is minimized. It uses binary search to determine the minimum possible maximum pages (mid). The is_possible function checks if books can be allocated within the given mid limit by iterating through the array and allocating books to students. Based on the result, the binary search adjusts the range until the optimal value is found. It handles edge cases like insufficient books for students.
Code:
#include <iostream>
#include <climits>
using namespace std;
// Function to check if a distribution is possible with the given max pages
bool is_possible(int books[], int n, int students, int max_pages) {
int allocated_students = 1;
int current_pages = 0;
for (int i = 0; i < n; i++) {
if (books[i] > max_pages) {
return false; // A single book has more pages than maxPages
}
if (current_pages + books[i] > max_pages) {
allocated_students++;
current_pages = books[i]; // Allocate to the next student
if (allocated_students > students) {
return false;
}
} else {
current_pages += books[i];
}
}
return true;
}
// Function to find the minimum pages
int min_pages(int books[], int n, int students) {
if (students > n) {
return -1; // Not enough books for each student
}
int low = 0, high = 0;
for (int i = 0; i < n; i++) {
high += books[i];
}
int result = INT_MAX;
while (low <= high) {
int mid = low + (high - low) / 2;
if (is_possible(books, n, students, mid)) {
result = mid; // Update result and try for a smaller maximum
high = mid - 1;
} else {
low = mid + 1; // Try for a larger maximum
}
}
return result;
}
int main() {
int books[] = {15, 24, 47, 70}; // Number of pages in each book
int n = sizeof(books) / sizeof(books[0]);
int students = 3;
cout << "Books array: ";
for (int i = 0; i < n; i++) {
cout << books[i] << " ";
}
cout << endl;
int result = min_pages(books, n, students);
if (result != -1) {
cout << "Minimum pages that can be allocated: " << result << endl;
} else {
cout << "Not enough books for all students." << endl;
}
return 0;
}
Output:
2. Minimum Capacity Required to Ship Packages Within D Days
This program calculates the minimum capacity of a ship needed to transport all packages within a given number of days. It uses binary search to find this capacity. The is_possible function checks if a given capacity can ship all packages within the required days by iterating through the packages and splitting loads into days when the capacity is exceeded. The binary search narrows the range of capacities until the minimum feasible capacity is found.
Code:
#include <iostream>
#include <climits>
using namespace std;
// Function to check if it is possible to ship all packages within `days` using `capacity`
bool is_possible(int weights[], int n, int days, int capacity) {
int current_load = 0;
int required_days = 1;
for (int i = 0; i < n; i++) {
if (weights[i] > capacity) {
return false; // A single package exceeds the capacity
}
if (current_load + weights[i] > capacity) {
required_days++;
current_load = weights[i]; // Start a new day with this package
if (required_days > days) {
return false;
}
} else {
current_load += weights[i];
}
}
return true;
}
// Function to find the minimum capacity required to ship packages within `days`
int min_capacity(int weights[], int n, int days) {
if (days > n) {
return -1; // Not enough packages to distribute over all days
}
int low = 0, high = 0;
for (int i = 0; i < n; i++) {
high += weights[i]; // Sum of all weights
if (weights[i] > low) {
low = weights[i]; // Maximum single package weight
}
}
int result = high;
while (low <= high) {
int mid = low + (high - low) / 2;
if (is_possible(weights, n, days, mid)) {
result = mid; // Update result and try for a smaller capacity
high = mid - 1;
} else {
low = mid + 1; // Try for a larger capacity
}
}
return result;
}
int main() {
int weights[] = {10, 20, 30, 40, 50, 60}; // Weights of the packages
int n = sizeof(weights) / sizeof(weights[0]);
int days = 4; // Number of days
cout << "Weights array: ";
for (int i = 0; i < n; i++) {
cout << weights[i] << " ";
}
cout << endl;
int result = min_capacity(weights, n, days);
if (result != -1) {
cout << "Minimum capacity required to ship packages within " << days << " days: " << result << endl;
} else {
cout << "It is not possible to ship packages within the given days." << endl;
}
return 0;
}
Output:
3. Find the Smallest Missing Positive Integer
This program finds the smallest missing positive integer by rearranging the array so that each positive number is placed at the index corresponding to its value (e.g., 1 at index 0). After rearrangement, it scans the array to identify the first index where the number does not match index + 1, which is the smallest missing positive integer. If all positions are correct, the result is n + 1.
Code:
#include <iostream>
using namespace std;
// Function to place each number in its correct position
void place_numbers(int arr[], int n) {
for (int i = 0; i < n; i++) {
while (arr[i] > 0 && arr[i] <= n && arr[arr[i] - 1] != arr[i]) {
swap(arr[i], arr[arr[i] - 1]); // Place arr[i] at its correct index
}
}
}
// Function to find the smallest missing positive integer
int smallest_missing_positive(int arr[], int n) {
place_numbers(arr, n);
// Check for the first missing positive integer
for (int i = 0; i < n; i++) {
if (arr[i] != i + 1) {
return i + 1;
}
}
// If all numbers from 1 to n are present
return n + 1;
}
int main() {
int arr[] = {3, 4, -1, 1}; // Input array
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
int result = smallest_missing_positive(arr, n);
cout << "The smallest missing positive integer is: " << result << endl;
return 0;
}
Output:
4. Median of Two Sorted Arrays
This program finds the median of two sorted arrays using binary search on the smaller array. It partitions both arrays into two halves such that all elements in the left half are smaller than or equal to those in the right half. The boundary elements of the partitions are used to calculate the median. If the combined array size is odd, the median is the maximum of the left partition; if even, it is the average of the maximum of the left partition and the minimum of the right partition.
Code:
#include <iostream>
#include <climits>
using namespace std;
// Function to find the median of two sorted arrays
double median_sorted(int arr1[], int m, int arr2[], int n) {
// Ensure binary search is performed on the smaller array
if (m > n) {
return median_sorted(arr2, n, arr1, m);
}
int low = 0, high = m;
int medianPos = (m + n + 1) / 2;
while (low <= high) {
int partition1 = low + (high - low) / 2;
int partition2 = medianPos - partition1;
int maxLeft1 = (partition1 == 0) ? INT_MIN : arr1[partition1 - 1];
int minRight1 = (partition1 == m) ? INT_MAX : arr1[partition1];
int maxLeft2 = (partition2 == 0) ? INT_MIN : arr2[partition2 - 1];
int minRight2 = (partition2 == n) ? INT_MAX : arr2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
// Correct partition found
if ((m + n) % 2 == 0) {
return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
} else {
return max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
// Move towards the left in arr1
high = partition1 - 1;
} else {
// Move towards the right in arr1
low = partition1 + 1;
}
}
// If no solution is found (should not happen for valid inputs)
return -1;
}
int main() {
int arr1[] = {1, 3, 5};
int m = sizeof(arr1) / sizeof(arr1[0]);
int arr2[] = {2, 4};
int n = sizeof(arr2) / sizeof(arr2[0]);
cout << "Array 1: ";
for (int i = 0; i < m; i++) {
cout << arr1[i] << " ";
}
cout << endl;
cout << "Array 2: ";
for (int i = 0; i < n; i++) {
cout << arr2[i] << " ";
}
cout << endl;
double median = median_sorted(arr1, m, arr2, n);
cout << "The median of the two sorted arrays is: " << median << endl;
return 0;
}
Output:
5. Number of Times a Sorted Array Is Rotated
This program uses binary search to find the number of times a sorted array has been rotated. It compares the elements at the low, mid, and high indices to locate the smallest element, which corresponds to the rotation count. The algorithm reduces the search space by checking which half of the array is sorted and continues the search in the unsorted half. The result is the index of the smallest element, representing the number of rotations.
Code:
#include <iostream>
using namespace std;
// Function to find the number of rotations in a sorted and rotated array
int rotation_count(int arr[], int n) {
int low = 0, high = n - 1;
while (low <= high) {
// If the array segment is already sorted, the minimum is at `low`
if (arr[low] <= arr[high]) {
return low;
}
int mid = low + (high - low) / 2;
int next = (mid + 1) % n; // Next element (circular index)
int prev = (mid - 1 + n) % n; // Previous element (circular index)
// Check if the mid element is the smallest
if (arr[mid] <= arr[next] && arr[mid] <= arr[prev]) {
return mid;
}
// Decide which half to search next
if (arr[mid] <= arr[high]) {
high = mid - 1; // Go to the left half
} else {
low = mid + 1; // Go to the right half
}
}
return -1; // This should not happen for a valid rotated sorted array
}
int main() {
int arr[] = {15, 18, 2, 3, 6, 12};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
int rot_count = rotation_count(arr, n);
cout << "The array is rotated " << rot_count << " times." << endl;
return 0;
}
Output:
Day 14 showcased the power of Binary Search in optimizing solutions for a wide range of complex problems. By adapting the algorithm to fit specific constraints, today’s tasks reinforced the efficiency and versatility of Binary Search. These exercises have deepened my understanding of how to apply this technique in more advanced problem-solving scenarios. Excited for what’s next! 🚀