Table of contents
- Q1. Solve the "allocate minimum number of pages" problem using binary search.
- Q2. Solve the "minimum capacity required to ship packages within d days" problem.
- Q3. Solve the "find the smallest missing positive integer" problem.
- Q4. Solve the "median of two sorted arrays" problem using binary search.
- Q5. Solve the "number of times a sorted array is rotated" problem.
Today, I delved into advanced searching problems, focusing on applying Binary Search in creative ways. I tackled challenges like allocating the minimum number of pages, determining the minimum capacity required to ship packages within a given number of days, and finding the smallest missing positive integer. Additionally, I solved the problem of finding the median of two sorted arrays and determining the number of times a sorted array is rotated. These problems enhanced my ability to adapt Binary Search to diverse scenarios, solidifying its role as a cornerstone of efficient problem-solving.
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. Solve the "allocate minimum number of pages" problem using binary search.
#include <iostream>
using namespace std;
#include <vector>
// Function to check if a given maximum allowed pages is valid
bool isValid(vector<int> &arr, int n, int k, int max_allowed_pages){
int noofstudents = 1, pages = 0; // Start with one student and zero pages allocated
for(int i = 0; i < n; i++){
// If a single book exceeds max_allowed_pages, allocation is not possible
if(arr[i] > max_allowed_pages){
return false;
}
// Add pages to the current student if within the limit
if(pages + arr[i] <= max_allowed_pages){
pages += arr[i];
}
// Assign to a new student if pages exceed the limit
else {
noofstudents++;
pages = arr[i];
}
}
// Check if the number of students required is within the allowed limit
return noofstudents <= k;
}
// Function to find the minimum number of pages to allocate
int min_no_pages(vector<int> &arr, int n, int k){
// If students are more than books, allocation is not possible
if(k > n){
return -1;
}
int sum = 0;
for(int i = 0; i < n; i++){
sum += arr[i]; // Calculate total pages
}
int start = 0, end = sum; // Binary search boundaries
int ans = -1; // To store the minimum valid result
while(start < end){
int mid = start + (end - start) / 2; // Calculate mid value (max allowed pages)
// If mid is valid, it could be the answer
if(isValid(arr, n, k, mid)){
ans = mid;
end = mid; // Narrow the search space to smaller valid values
}
// If mid is not valid, increase the lower bound
else {
start = mid + 1;
}
}
return ans; // Return the minimum valid pages
}
int main()
{
int n, k;
cout << "Enter no of books: ";
cin >> n; // Input the number of books
cout << "No. of pages of each book?: ";
vector<int> arr(n);
for(int i = 0; i < n; i++){
cin >> arr[i]; // Input pages for each book
}
cout << "How many students?: ";
cin >> k; // Input the number of students
// Output the minimum pages that can be allocated
cout << min_no_pages(arr, n, k) << endl;
return 0; // Indicate successful execution
}
This code solves the problem of allocating books to a given number of students such that the maximum number of pages assigned to a student is minimized. It uses a binary search approach to find the optimal solution. The isValid function checks if it's possible to allocate the books to k students without any student receiving more than max_allowed_pages by iterating through the books and tracking the current number of pages assigned to each student. If a student exceeds the page limit, a new student is assigned the next books. The min_no_pages function performs binary search over the possible values for the maximum allowed pages, ranging from the largest single book to the total sum of pages. It iteratively narrows down the search space, checking if a valid allocation exists for each midpoint value. The result is the smallest maximum pages that can be allocated to any student while keeping the number of students within the limit. The program takes input for the number of books, the number of students, and the pages in each book, then outputs the minimum number of pages that can be allocated. If the number of students exceeds the number of books, allocation is not possible.
Q2. Solve the "minimum capacity required to ship packages within d days" problem.
#include <iostream>
using namespace std;
// Function to calculate the number of days required to ship packages with a given capacity
int daysRequired(int weights[], int n, int capacity) {
int days = 1, load = 0; // Initialize days and current load
for (int i = 0; i < n; i++) {
if (weights[i] + load > capacity) { // If adding current weight exceeds capacity
days += 1; // Increment days
load = weights[i]; // Start new load with current weight
} else {
load += weights[i]; // Add current weight to the load
}
}
return days; // Return total days required
}
// Function to find the minimum capacity to ship within the given days
int noOfDays(int weights[], int n, int days) {
int max = 0; // Variable to store the sum of all weights
for (int i = 0; i < n; i++) {
max += weights[i]; // Calculate total weight
}
int start = 0, end = max; // Initialize binary search boundaries
while (start <= end) {
int mid = (start + end) / 2; // Calculate mid as potential capacity
if (daysRequired(weights, n, mid) <= days) { // If mid capacity works
end = mid - 1; // Reduce the search space to find smaller capacity
} else {
start = mid + 1; // Increase the search space for larger capacity
}
}
return start; // Return the minimum capacity found
}
int main() {
int n, days;
cout << "Enter no of containers: ";
cin >> n; // Input number of containers
cout << "Weight of each container?: ";
int weights[n];
for (int i = 0; i < n; i++) {
cin >> weights[i]; // Input weights of containers
}
cout << "No of days? : ";
cin >> days; // Input number of days
// Output the minimum capacity required
cout << noOfDays(weights, n, days) << endl;
return 0; // Indicate successful execution
}
This code solves the problem of determining the minimum capacity required for shipping containers within a given number of days. It utilizes a binary search approach to find the optimal capacity. The daysRequired function calculates the number of days needed to ship all containers given a particular capacity. It does this by iterating over the container weights and adding them to the current load; if the load exceeds the given capacity, it starts a new day with the current container. The noOfDays function performs a binary search over the possible capacities, ranging from the weight of the heaviest container to the total sum of all containers' weights. It checks for each mid-point capacity if the number of days required is within the allowed days. The program finally outputs the minimum capacity that ensures all containers are shipped within the given number of days. The input consists of the number of containers, their weights, and the number of days, and the output is the minimum shipping capacity required.
Q3. Solve the "find the smallest missing positive integer" problem.
#include <iostream>
using namespace std;
#include <algorithm>
// Function to find the smallest missing positive integer
int findSmallestMissing(int arr[], int n) {
for (int i = 0; i < n; i++) {
// Place each positive number within the range [1, n] in its correct position
while (arr[i] > 0 && arr[i] <= n && arr[arr[i] - 1] != arr[i]) {
swap(arr[arr[i] - 1], arr[i]); // Swap to move the number to its correct index
}
}
for (int i = 0; i < n; i++) {
if (arr[i] != i + 1) {
return i + 1; // Return the smallest missing positive integer
}
}
return n + 1; // If all numbers from 1 to n are present, return n+1
}
int main() {
int n;
cout << "Enter length of array: ";
cin >> n; // Input the length of the array
cout << "Enter elements of the array: ";
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i]; // Input the elements of the array
}
// Output the smallest missing positive integer
cout << findSmallestMissing(arr, n);
return 0; // Indicate successful execution
}
This code solves the problem of finding the smallest missing positive integer in an unsorted array. The findSmallestMissing function first rearranges the elements of the array so that each positive number within the range [1, n] is placed at the correct index (i.e., arr[i] should be at index arr[i] - 1). It uses a while loop to perform swaps until the array is partially sorted such that each valid number is in its correct position. After rearranging, the function then scans through the array to find the first index where the number is not equal to index + 1. This index+1 is the smallest missing positive integer. If no such index is found (meaning all numbers from 1 to n are present), the function returns n+1 as the smallest missing integer. The main function takes user input for the array size and its elements, then outputs the smallest missing positive integer.
Q4. Solve the "median of two sorted arrays" problem using binary search.
#include <iostream>
using namespace std;
#include <vector>
#include <climits>
// Function to find the median of two sorted arrays
double find_median(vector<int> arr1, vector<int> arr2){
int n1=arr1.size(); // Size of the first array
int n2=arr2.size(); // Size of the second array
// Ensure the first array is smaller to reduce the binary search range
if(n1>n2) return find_median(arr2,arr1);
int low=0, high=n1; // Binary search boundaries
int left=(n1+n2+1)/2; // Total number of elements in the left partition
int n=n1+n2; // Total number of elements in both arrays
while(low<=high){
int mid1=(low+high); // Partition index for the first array
int mid2=left-mid1; // Partition index for the second array
// Left and right partition values for both arrays
int l1=INT_MIN, l2=INT_MIN;
int r1=INT_MAX, r2=INT_MAX;
// Assign right partition values if within bounds
if(mid1<n1) r1=arr1[mid1];
if(mid2<n2) r2=arr2[mid2];
// Assign left partition values if within bounds
if(mid1-1>=0) l1=arr1[mid1-1];
if(mid2-1>=0) l2=arr2[mid2-1];
// Check if the partition is valid
if(l1<=r2 && l2<=r1){
if(n%2==1) return max(l1,l2); // Return the max of left partition for odd-length arrays
return ((double)(max(l1,l2)+min(r1,r2)))/2.0; // Return the average for even-length arrays
}
// Adjust binary search range
else if(l1>r2) high=mid1-1;
else low=mid1+1;
}
return 0; // Default return value in case of failure
}
int main()
{
int n1,n2;
cout<<"Enter length of first array: ";
cin>>n1; // Input size of the first array
vector<int> arr1(n1);
cout<<"Enter elements of the array: ";
for(int i=0;i<n1;i++){
cin>>arr1[i]; // Input elements of the first array
}
cout<<"Enter length of second array: ";
cin>>n2; // Input size of the second array
vector<int> arr2(n2);
cout<<"Enter elements of the array: ";
for(int i=0;i<n2;i++){
cin>>arr2[i]; // Input elements of the second array
}
// Output the median of the two arrays
cout<<"The median of the two arrays are: "<<find_median(arr1,arr2);
return 0; // Indicate successful program execution
}
This code finds the median of two sorted arrays using a binary search approach to optimize the time complexity. The function find_median takes two sorted arrays, arr1 and arr2, as input. It ensures that the first array is the smaller one to reduce the search space. Then, it uses binary search to partition the two arrays such that the left partition contains half of the combined elements. The partition is adjusted by comparing values from both arrays to ensure valid partitions: the largest element of the left partition is smaller than the smallest element of the right partition. Once a valid partition is found, if the combined number of elements is odd, it returns the maximum of the left partition. If even, it returns the average of the largest element in the left partition and the smallest element in the right partition. The main function takes user inputs for the arrays and their lengths, then calls find_median to compute and output the median of the two arrays. The solution ensures optimal time complexity of O(log(min(n1, n2))).
Q5. Solve the "number of times a sorted array is rotated" problem.
#include <iostream>
using namespace std;
// Function to find the number of times a sorted array has been rotated
int no_of_times_rotated(int arr[], int n) {
int low = 0, high = n - 1; // Initialize search boundaries
while (low <= high) {
// If the array is already sorted, it hasn't been rotated
if (arr[low] <= arr[high])
return low;
int mid = low + (high - low) / 2; // Calculate mid to prevent overflow
// Check if mid is the pivot (smallest element)
int prev = (mid - 1 + n) % n; // Previous element (circular index)
int next = (mid + 1) % n; // Next element (circular index)
if (arr[mid] <= arr[prev] && arr[mid] <= arr[next])
return mid;
// Decide the search space
if (arr[mid] >= arr[low])
low = mid + 1; // Search in the right half
else
high = mid - 1; // Search in the left half
}
return -1; // Return -1 if no rotation is found (edge case, should not occur)
}
int main() {
int n;
cout << "Enter length of array: ";
cin >> n; // Input array length
cout << "Enter elements of the array: ";
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i]; // Input array elements
}
// Output the number of rotations
cout << "The number of times the array has been rotated: " << no_of_times_rotated(arr, n);
return 0; // Indicate successful execution
}
This code finds the number of times a sorted array has been rotated using a binary search approach. The function no_of_times_rotated identifies the pivot element (the smallest element) in the rotated array, which corresponds to the number of rotations. It does so by comparing the mid element with its neighbors in each iteration. If the array is already sorted (i.e., the element at the start is less than or equal to the element at the end), it returns 0 rotations. Otherwise, it adjusts the search boundaries by checking whether the left or right half is sorted, narrowing the search space until the pivot is found. The index of the pivot is returned, indicating the number of rotations. This solution has a time complexity of O(log n), making it efficient for large arrays.
Today's practice deepened my understanding of advanced applications of Binary Search. From solving allocation problems to calculating medians and rotations in arrays, I learned how versatile and powerful this algorithm is in tackling complex challenges. These exercises have equipped me with valuable techniques to handle intricate searching problems more effectively. I look forward to exploring even more advanced topics in the days ahead!