Help needed in Mathematical Interview Problem

Правка en1, от vishudon, 2022-09-23 23:08:07

Hi there,

I hope you all are doing very good. Today, I had a discussion with my friend. He was asked below mathematical problem in his SDE interview by the technical team. But, he was not able to come up with any solution of that problem. Later, when he discussed that with me. I think I was able to solve 1st part of the problem, but I too got stuck on the 2nd part. So, Kindly help us in understanding what should be the solution of the 2nd part of the below problem.

Problem:

Given P = A*B*C, where A = 3y, B = 2y+1, and C = 2^y

Also, some value K is given, which is fixed. And, it is obvious that for all y>0, value of P will increase. So, we need to answer two parts:

  • (i) Find the minimum value of y such that P>=K in O(logK) time.
  • (ii) Find the minimum value of y such that P>=K in O(log(logK)) time.

My Solution of 1st part: Since for all y>0, value of P is increasing. So, we can apply binary search here. We will start range of y from 1 to infinity, and we will check if P>=K holds or not, for a particular value of y. In this way, we can find minimum value of y which satisfy the given property.

My views on 2nd part: If we further explore value of P like this:

  • P = A * B * C
  • P = A * B * (2^y)
  • P/(AB) = 2^y // got stuck here

Here, at this step, I think if we apply log on both sides, something useful can come out. But, not able to solve it further. I'm not sure about this approach whether it is correct or not, but still tried hard to come up with the solution. But I couldn't solve. So, if possible, Please help me.

Anyone can suggest a solution for the same ? Any help will be appreciated. Thanks (in advance) for your time and support.

Теги mathematical, interview

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский vishudon 2022-09-23 23:08:07 1786 Initial revision (published)