103.md

Solution

Submission link - https://bigfrontend.dev/problem/implement-Math-sqrt/discuss/309

/**
 * @param {any} x
 * @return {number}
 */
function mySqrt(x) {
  
  /** === Using the Babylonian square-root algorithm 👇 === */
  // https://blogs.sas.com/content/iml/2016/05/16/babylonian-square-roots.html
  
  // special cases
  if(x == 0 || x == Infinity) return x;
  if(typeof x != 'number' || x == -Infinity || x < 0 || Number.isNaN(x) ) return NaN;
  
  // till what precision we want to find square root of a number.
  // doesn't matter in this case as we want to return only integer part.
  const precision = 0.00001;
  let guess = x / 2; // usually middle of 'x'
  
  let lastGuess = x / 2; // we compare the guess with last guess, we loop till we their difference crosses 'precision'

  while(true) {
    guess = (guess + x / guess) / 2; // Babylonian square-root algorithm
    if(lastGuess - guess <= precision) return Math.trunc(guess); // return only integer part
    lastGuess = guess; // update last guess with guess
  }
}

Short story

I don't understand how can FAANG ask such questions. Definitely, scientists and mathematicians are there to come up with algorithms.
As an engineer, my job is to implement them. Though it was a bit effortful task it wasn't something that I'm proud of (as I understood algorithm and just implemented it).

Okay, I'm stopping rant. That's just my feeling^* right now.

^*Subject to change any time.

Algorithm -

1. We first set accuracy (as precision const in code), to determine how much close do we want our square root result
   Remember we don't need to go too deep as we just want integer (problem requirement) so up to 3-4 decimals is enough.
2. We first take an initial guess. This is usually a positive number and half of the input say, guess = x / 2
3. We need to improve our guess by applying formula - guess = (guess + x / guess) / 2. 👈 This is Babylonian's main part
4. We repeat the process until our previous guess and current guess is equal to (or less than) precision
   Because that shows that we are very near to getting value.
5. We take out the integer part using Math.trunc method
6. We also update lastGuess in each iteration to compare that in the next iteration

Time complexity	Space complexity
Help me with it	Help me with it

Code overview -

1. We first handle all the edge cases, I did when cases failed for them. (💡 Tip: Better to ask interviewer)
2. We set precision - const precision = 0.00001; Feel free to lower the value or go up to only 2-3 decimal places
3. For the first iteration, we initialize guess and lastGuess values by x / 2
4. We want to repeat the process until it reaches a point where lastGuess and guess is equal (or less than) precision.
5. We break while-loop inside rather than having a condition in a while-loop. It's a preference thing.

Resources -

1. The Babylonian method for finding square roots by hand

---

Twitter: (@knowkalpesh)