Multiplication Table CSES Solution | CSES Problem Set | Binary Search
Raunit Verma - in CSES
Views: 2
Find the middle element when the numbers in an n \times n multiplication table are sorted in increasing order. It is assumed that n is odd. For example, the 3 \times 3 multiplication table is as follows:
#include<bits/stdc++.h>
using namespace std;
#define int long long int
bool helper(int n,int x){
int cnt = 0;
int mid = (n*n + 1)/2;
for(int i = 1; i<=n; i++){
int div = (x/i);
cnt+=min(div,n);
}
return cnt>=mid;
}
int32_t main(){
int n;
cin>>n;
int low = 1, high = n * n + 10, mid;
while(high>=low){
mid = low + (high - low) / 2;
if(helper(n,mid)){
high = mid - 1;
}else{
low = mid + 1;
}
}
cout<<low<<endl;
return 0;
}Tagscsesmultiplication tablemultiplication table cses solutionmultiplication table cses
Raunit Verma
Technical Writer at CodingKaro
Share this on
