This content originally appeared on DEV Community and was authored by Adriana DiPietro
☁️☁️☁️
Hi programmers + coders alike !
Today, we will be walking through two (2) LeetCode challenges: Sqrt(x) and Valid Perfect Square. I decided to pair these challenges together in a walkthrough because they relate to each other AND show the various ways to approach a solution.
Here are the links to the challenges: Sqrt(x) and Valid Perfect Square. Go ahead and pull the first challenge up on your end + let's get started :)
Sqrt(x)
Instructions + Examples
Let's take a look at the instructions provided by LeetCode:
Given a non-negative integer 'x', compute and return the square root of 'x'.
Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.
Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.
From the instructions, we can resolve a few things:
- Input is a positive integer.
- Output is a positive integer; decimal points must be truncated (taken off).
- We cannot use any exponent operator.
The instructions are pretty straight-forward. However, the truncated decimal might be something new for you. (It was for me!) Growing up, in math class we always rounded decimals to the nearest whole number. For this assignment, we are going to truncate the decimal.
If we look to the example LeetCode provides, we can see exactly what this looks like:
// Example 2
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
The square root of 8 is not rounded to the nearest whole number; instead, the decimals are just chopped off. To me, this is strange, but hey, I do not make the instructions here.
Approach + Solution
Since this is a math-based question, we can consider a wide slew of built in Math methods provided in JavaScript. These built-in Math methods are both life and time savers. Here is a link to a good chunk of Math methods. Bookmark or save this link!!
If we return to our goals of this challenge, we need to achieve two (2) things:
- Return the square root any positive integer.
- Return the output as a positive integer (no floats!)
To achieve the first goal, JavaScript provides 'Math.sqrt(x)'. According to the link above, this method 'returns the positive square root of the given input'. Wow! Exactly what we need.
So, let's build this out:
// Starting by building the foundation of a function that takes in a parameter of 'x'
function mySqrt(x){
// Then, declare and assign a variable to the result of Math.sqrt(x) method.
let squareRoot = Math.sqrt(x)
return squareRoot
}
At this point, if we were to pass in an integer of '100', we would receive an output of '10'. Nice! That works! However, if we were to pass in an integer of '200', we would receive an output of '14.142135....' Well, yea that is correct, but remember the instructions: we need to return a truncated decimal. So, we need to return solely '14'.
If we continue to look at that trusty goldmine of built-in Math methods, we may come across 'Math.trunc(x)'. This method 'returns the integer portion of the given input, removing any fractional digits.' Actually perfect! Let's add this functionality to our code:
// Starting by building the foundation of a function that takes in a parameter of 'x'
function mySqrt(x){
// Then, declare and assign a variable to the result of Math.sqrt(x) method.
// Then, we wrap Math.trunc() around Math.sqrt(x).
let squareRoot = Math.trunc(Math.sqrt(x)))
return squareRoot
}
Try this out in your console with an input of x = 250.
Did you receive an output of '15'? If you did, good! Our code works.
Valid Perfect Square
Instructions + Examples
Onto our next challenge, let's look at the instructions:
Given a positive integer 'num', write a function which returns 'True' if 'num' is a perfect square. Otherwise returns 'False'.
*Follow up: Do not use any built-in library function such as sqrt
From these instructions, we can resolve a few things:
- Input is a positive integer.
- Output is a boolean: true or false.
- We CANNOT use any built-in JavaScript methods, like we did in the previous challenge.
Let's look at the examples provided:
Example 1:
Input: num = 16
Output: true
Example 2:
Input: num = 14
Output: false
Alright -- simple enough. However, the instructions specifically stated to NOT use any built-in Math methods. This is our time to shine and revert back to seventh grade algebra! Let's get it.
Approach + Solution
What is a perfect square? It is an integer, when taken the square root of, returns a positive integer. We know a few: 4, 9, 16, 25, 100...
But how do we formulate a test (ahem, our code) to figure this out? We can start by creating a formula that outputs the square root of any given positive integer.
What is the math formula equivalent of the square root operator? It's the exponent of one-half. Try it out on a calculator.
Using the exponent operator (**), here is what we can code:
function isPerfectSquare(num) {
let squareRoot = (num ** 0.5)
return squareRoot
}
If we pass the number 100 into the function, we should be returned the integer 10. Ok - but what if we pass in 12? We receive 3.464101.... Yes - that is the square root of 12, but remember we want to receive an output of either true or false based on num's validity as a perfect square.
If we compare our two outputs: 10 and 3.464101, one is an integer and the other is a float (or decimal).
We can use the remainder operator (%). If our squareRoot produces a remainder when divided by 1, then we know it is NOT a perfect square.
Let's code this out:
function isPerfectSquare(num) {
let squareRoot = (num ** 0.5)
if (squareRoot % 1 === 0) {
return true
}
return false
}
Using our ol' faithful "if" statement, we can decipher that if our squareRoot variable does NOT produce a remainder, 'num' must be a perfect square. While if it does produce a remainder, 'num' is NOT a perfect square.
Summary + Recap
Within these two (2) examples, we can see the multiple approaches to solve a Math-related JavaScript question. Given specific instructions that inhibit our use of either built-in Math methods or arithmetic operators, we can resolve to do the opposite.
Go ahead and try to solve each question again, except switch the rules this time. A solution is always available -- we may just have to dig a little first.
REMEMBER
- Keep your code readable.
- Code in a way that makes sense to you.
- Approach code a few different ways to come to a solution.
- Ask questions.
- Keep coding!
☁️☁️☁️
Thank you for reading + coding along with me.
Please feel free to leave questions, suggestions or comments below.
Please be kind to everyone as we are all trying to learn.
This content originally appeared on DEV Community and was authored by Adriana DiPietro
Adriana DiPietro | Sciencx (2021-12-07T19:02:36+00:00) LeetCode WalkThru: ‘Sqrt(x)’ and ‘Valid Perfect Square’. Retrieved from https://www.scien.cx/2021/12/07/leetcode-walkthru-sqrtx-and-valid-perfect-square/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.