HackerRank Past Contest

[itadakimas]

HackerRank

can anyone help me find the correct approach to solve this problem . I’ve tried using naive approach and also tried using priority queues to get the kth smallest element from the given matrice but both the solutions are fetching me runtime error for few TestCases/partially correct because of big constraints.

Do share your approach . Thankyou in adv

[cubefreak777]

Crack the Code by CognoAI

I don’t have a clever solution for matrix problem but you can always binary search the answer though. #include "bits/stdc++.h" using namespace std ; #define int long long signed main(){ int n,k ; cin >> n >> k ;--k; auto ok = [&](int x)->int{ int c=0 ; for(int i=1;i<=n;i++) c+=min(x/i,n) ; return c<=k ; } ; int lb = 1,rb=n*n ; while(lb<rb){ int mb=(lb+rb)/2 ; if(ok(mb)) lb =mb+1 ; else rb=mb ; } cout << lb ; }

I’ve discussed my solution in this thread, feel free to ping me if you don’t get it.

[itadakimas]

Thankyou so much senior .
but i’m afraid i am not able to understand this part of code .

 auto ok = [&](int x)->int{
    int c=0 ;
    for(int i=1;i<=n;i++)
      c+=min(x/i,n) ;
    return c<=k  ;
  } ;

[cubefreak777]

Are you familiar with lambda functions? or you didn’t get the logic itself ?

[ssrivastava990]

#include "bits/stdc++.h"
using namespace std ;
#define int long long 

bool ok(int x , int n){
    int c=0 ;
    for(int i=1;i<=n;i++)
      c+=min(x/i,n) ;
    return (c<=k);
  } 

signed main(){
  int n,k ;
  cin >> n >> k ;--k;
  int lb = 1,rb=n*n ;
  while(lb<rb){
    int mb=(lb+rb)/2 ;
    if(ok(mb,n))
      lb =mb+1 ;
    else
      rb=mb  ;
  }
  cout << lb  ;
}

If u don’t know lambda function then : " Lambda expression in C++ - GeeksforGeeks"

[itadakimas]

i didn’t get the logic behind choosing the minimum between (x/i, n) and adding up them to compare with k.

[itadakimas]

Thankyou

[cubefreak777]

Crack the Code by CognoAI

See you if I give you a number x then you can check whether it’s the kth number or not by counting the total number of elements which are less than x but are present in the matrix. You can do so by going to each ith row and adding \displaystyle\frac{x}{i} as it’s contribution. And rest is trivial binary search.

Crack the Code by CognoAI

Alright if you observe the matrix for any N it’d look like. 1 \ 2 \ 3 \ 4 \ \ 5 \dots\ 2 \ 4 \ 6 \ 8 \ 10 \dots 3 \ 6 \ 9 \ 12 \ 15 \dots \vdots It is clearly evident that the ith row contains multiples of i. Second thing to note is the following question. How many multiples of i do we have which are less than a given number x. If you scribble it on paper you can observe that it is exactly \displaystyle\frac{x}{i}. And we can also see it intuitively that why is this the c…

Have you checked these already? if you still don’t get it do let me know

[itadakimas]

Thankyou @cubefreak777 for this perfect explaination. Now i’ve understood it .