# ECAUG205 - Editorial

Author: Akash Kumar Bhagat
Tester: Sandeep Singh
Editorialist: Akash Kumar Bhagat

Easy- Med

Binary Search

# PROBLEM:

You have N notebooks of different types numbered 1 to N with each books containing A_i number of pages respectively. Chefs Motive is to split these books into K separate notebooks having an equal number of pages.

No notebook can have pages from 2 or more different notebook type.

# EXPLANATION:

This is a typical Binary Search Problem in which one has to maximize the number of pages in the new notebooks. Here it is possible to make K notebooks with fewer pages, like 1,2,3,4… pages in each new notebook. So one has to find the maximum number of pages on can fit in each book. To find this upper limit one can use Binary Search.

For example:
N=4 , K=11
A=[802,743,457,539]

``````	    PAGES:		         	1  2  3  4  5 ......  198  199  200  201  202
POSSIBLE TO DISTRIBUTE(1/0)  : 	1  1  1  1  1 ......   1    1    1    0    0
``````

In this case, the answer will be 200 as this is the upper limit of the number of pages that one can split those N-type of notebooks to 11 kids.

### TIME COMPLEXITY:

O(N*log n), where N is the types of notebook and n is the total search range.

# SOLUTIONS:

Python 3.7
``````def chk(x):
temp=0
for i in a:
temp+=i//x

return temp>=k

for _ in range(int(input())):
n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
l,r=0,max(a)+1
while(r>l+1):
mid=(l+r)//2
#print("*",mid,l,r)
if(chk(mid)):
l=mid
else:
r=mid

print(l)

``````
CPP
``````
#include <bits/stdc++.h>
#define ll long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ln cout << '\n'
#define mod 1000000007
#define MxN 100005
#define all(x) x.begin(), x.end()
using namespace std;

bool check(ll pages, int k, vector <ll>& books){

ll cnt  = 0;

for(ll book : books){
cnt += book / pages;

if(cnt >= k)
return 1;
}
return 0;
}

void solve(){

int i, j, n, k;
ll sum = 0;
cin >> n >> k;
vector <ll> arr(n);
ll lft = 1, rgt = 0;

for(i = 0; i < n; ++i){
cin >> arr[i];
sum += arr[i];
rgt = max(rgt, arr[i]);
}
//rgt = max(rgt, sum / k);
rgt++;

while(lft < rgt){

ll mid = (lft + rgt ) / 2;

if(check(mid, k, arr))
lft = mid + 1;
else
rgt = mid;
}
cout << lft - 1 << '\n';
}
int main(){

ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);

#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif

int t = 1;
cin >> t;
while(t--)
solve();
}

``````
5 Likes

Can someone tell me why do we need this line

rgt++

I had implemented the same concept except that I missed the above line and it was showing error in some test case. Can someone tell me which kind of border test case might have been getting failed due to this ?

hey @abhinaviitj
rgt++ is required because the answer can be the maximum pages of all,
if you won’t do that, the following tc will fail.

1
2 1
10 9

Answer should be 10, but if rgt=max(arr)(which is 10) the answer will never 10,