class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
//merge these two arrays and find the median of the newly sorted array
int arr[] = new int[nums1.length + nums2.length];
sort(nums1,nums2,arr);
return findMedian(arr);
}
public double findMedian(int arr[]){
int mid = arr.length/2;
if(arr.length %2!=0){
return (double)arr[mid];
}
else{
return (double)((double)(arr[mid]+arr[mid-1])/2);
}
}
public void sort(int a[], int b[], int arr[]){
int p = 0;
int q = 0;
int k =0;
while(p<a.length && q < b.length){
if(a[p]<b[q]){
arr[k] = a[p++];
}
else{
arr[k] = b[q++];
}
k++;
}
while(p<a.length){
arr[k++] = a[p++];
}
while(q<b.length){
arr[k++] = b[q++];
}
}
}
Explanation:
given :
Input: ‘n’ = 4 ‘m’ = 2
‘arr’ = [12, 34, 67, 90]
we are given list of books arr, where arr[i] has pages in the book i
we are given m students as well, we have to allocate books such that all the books are contiguously distributed among m students(same book is not assigned to two students)
now there can be a lot of contiguous distributions of the book
let say arr = [12, 34, 67, 90],and m = 2
We, will have two partitions of the arr
like 12|34,67,90 > student 1 will have 12 pages, student 2 will have 191 pages
or 12,34| 67,90 > student 1 will have 55 pages, student 2 will have 157 pages
or
12,34,67|90 > student 1 will have 113 pages, student 2 will have 90 pages
among all the distribution, maximum minimum no. of pages allocated is 113
Intuition:
We have to choose minimum no. of pages that a student can hold such that all the students get at least one book
In the given example the max page count is 90, this can be the min page that the student will have to hold ( else book with page 90 can not be held by any student)
now we will try to see if it is the maximum minimum no. of pages or not
[12, 34, 67, 90], students = 2
iteration 1 with 90:
for student 1
12+34<90 true, but 12+34+67 >90 hence student 1 will hold 12+34 = 46 pages
for student 2
67+90 > 90 hence student 2 will hold 67 pages
But there is one book with 90 pages remaining for this to be allocated we will need another student
This will increase the student count to 3, which is not possible
Hence the maximum minimum book can not be 90
We will try with Iteration 91,92,………MaxMinPage unless we find the max min page that can be used to assign all the book to all the 2 students that will be our answer
note: we can not go on forever …we will have to stop at some page count right, so the max page count will be sum(arr)
//for more details refer : https://youtu.be/Z0hwjftStI4?t=1412 for binary search
///brute force:
//tc: O(sum-max)*n
import java.util.*;
public class Solution {
public static int findPages(ArrayList<Integer> arr, int n, int m) {
if(m>n) return -1;
// brute force
int maximum = Integer.MIN_VALUE;
int sum =0;
for(int i : arr){
maximum = Integer.max(i,maximum);
sum+=i;
}
for(int max = maximum;max<=sum;max++){
int student = allocate(max,arr);
if(student ==m) return max;
}
return -1;
}
public static int allocate(int pages, ArrayList<Integer> arr){
int student =0;
int currentPagesForStudent =0;
for(int i =0;i<arr.size();i++){
if(currentPagesForStudent+arr.get(i)<=pages){
currentPagesForStudent+=arr.get(i);
}
else{
currentPagesForStudent = arr.get(i);
student++;
}
}
return student+1;
}
}
///binary search://tc : O((log(sum-maximum-1)*(n)), where n is the arr.size()
import java.util.*;
public class Solution {
public static int findPages(ArrayList<Integer> arr, int n, int m) {
// book allocation impossible
if (m > n)
return -1;
int low = Collections.max(arr);
int high = arr.stream().mapToInt(Integer::intValue).sum();
while (low <= high) {
int mid = (low + high) / 2;
int students = allocate(mid,arr);
if (students > m) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
public static int allocate(int pages, ArrayList<Integer> arr){
int student =0;
int currentPagesForStudent =0;
for(int i =0;i<arr.size();i++){
if(currentPagesForStudent+arr.get(i)<=pages){
currentPagesForStudent+=arr.get(i);
}
else{
currentPagesForStudent = arr.get(i);
student++;
}
}
return student+1;
}
}
Top comments (0)