# LeetCode Pow(x, n) by Hand

Published on Sep 11th 2020Duration: 22:42

Interview practice: I solve a code challenge: Pow(x, n) on LeetCode by hand.

## Transcript

The following transcript was automatically generated by an algorithm.

• 00:00 : all right folks i'm going to implement
• 00:02 : the
• 00:03 : power function uh this is a
• 00:06 : challenge on the lead code website
• 00:11 : which is simply to implement the power
• 00:14 : function
• 00:15 : usually the standard library of your
• 00:17 : programming language would give this to
• 00:19 : you but
• 00:19 : in this case we're going to have to
• 00:22 : write
• 00:23 : our own it gave us a few examples
• 00:27 : such as 2 to the 10th power is
• 00:31 : the 1024
• 00:35 : some companies they don't allow you to
• 00:38 : actually execute the code so i'm going
• 00:41 : to
• 00:42 : practice doing it with only pen
• 00:45 : and paper a good damp towel here
• 00:48 : to erase off
• 00:53 : things a little faster if i need to
• 00:56 : okay and i'm going to get started so the
• 00:59 : examples are
• 01:01 : if the input is x is
• 01:05 : 2 and then n is
• 01:09 : 10 then the output
• 01:13 : then the output should be
• 01:18 : one zero two four point zero
• 01:21 : so like we're assuming floating point
• 01:23 : numbers here
• 01:26 : and then the next case is
• 01:34 : okay so i think this
• 01:38 : is just a iterative um
• 01:43 : iterative multiplication problem i
• 01:45 : believe
• 01:46 : uh because if you want to get the power
• 01:50 : of
• 01:51 : 2 so 2 to the 10th power is
• 01:54 : simply 2 multiplied by itself 10 times
• 01:58 : so you could make a loop right so for
• 02:04 : i
• 02:07 : equals i don't know 1 to 10.
• 02:11 : i'm writing in pseudo basic
• 02:15 : i guess uh i have a
• 02:18 : product i initialize it at
• 02:22 : one then i can do
• 02:26 : product equals
• 02:29 : product
• 02:33 : times two and
• 02:36 : for the uh that should give us what
• 02:39 : we're after here
• 02:40 : um however
• 02:44 : that doesn't work if the exponent
• 02:48 : is negative so in the case where the
• 02:50 : exponent is negative
• 02:53 : we should multiply it by
• 02:59 : if exponent is
• 03:02 : negative
• 03:07 : then we actually want to
• 03:11 : do product
• 03:14 : equals product
• 03:18 : times one over two
• 03:24 : of course this doesn't work just for two
• 03:26 : but uh
• 03:27 : it should work for everything uh for
• 03:30 : any base okay so
• 03:33 : let's try to write this algorithm so
• 03:37 : i'm going to write this let's write this
• 03:40 : in python
• 03:41 : because python is more terse in them
• 03:45 : and i don't have to write so much
• 03:52 : python may already have a pal function
• 03:54 : so i might have to write it
• 03:56 : with a different name so i'm gonna write
• 03:58 : it
• 03:59 : call it my pal my pal
• 04:04 : um it's gonna receive an x and an
• 04:07 : n we're gonna iterate through this sky
• 04:10 : end times basically so
• 04:14 : let's say for
• 04:20 : i in
• 04:23 : range of
• 04:26 : n and i believe that will make it
• 04:29 : iterate
• 04:30 : n times uh forgot to initialize the
• 04:34 : product
• 04:37 : so product we're gonna
• 04:41 : initialize it is one
• 04:44 : and uh now we're gonna do our for loop
• 04:48 : i in range
• 04:54 : of n which in python
• 04:58 : uh in python if you don't know that
• 05:01 : gives you a less
• 05:04 : range of n like range of let's say range
• 05:08 : of
• 05:08 : five
• 05:13 : gives you a list that is 0
• 05:16 : 1 2 3 4.
• 05:21 : i believe although in the new version of
• 05:23 : python it doesn't give you an
• 05:25 : actual list it gives you something like
• 05:27 : a lazy list
• 05:29 : so it doesn't have to allocate the
• 05:31 : memory to
• 05:32 : if if it was 1 million it will
• 05:35 : actually allocate the memory to to
• 05:39 : store all those numbers um
• 05:42 : okay so
• 05:45 : iterating through this i'm gonna say
• 05:50 : if my n
• 05:53 : is greater than zero
• 05:57 : hold up will this work if it's a
• 06:00 : negative number
• 06:04 : uh
• 06:13 : i might have to handle it initially
• 06:20 : okay so this is what i'm gonna do i'm
• 06:22 : gonna say i'm gonna
• 06:24 : say each of these
• 06:27 : each of these guys is
• 06:30 : if each of the uh parts of the product
• 06:35 : what's what's the name for this each of
• 06:37 : the the base
• 06:38 : maybe maybe it's this is called the base
• 06:42 : um i'm gonna set up a base
• 06:46 : if n is negative the base is gonna be
• 06:51 : yeah i'm just gonna write this out um
• 06:55 : i'm gonna have a base which is
• 06:58 : normally x but if
• 07:02 : n is negative then let me change the
• 07:06 : base
• 07:07 : to 1 divided by x
• 07:12 : um now i'm ready to now this space is
• 07:16 : what i'm gonna multiply by
• 07:19 : multiply into the product at every uh
• 07:22 : iteration
• 07:23 : so if i is in
• 07:28 : range of n
• 07:33 : um did i say
• 07:36 : if i meant 4 for i
• 07:40 : in range of n then product is
• 07:44 : product
• 07:47 : times base
• 07:53 : i'm going to return
• 07:56 : the product at the end
• 08:00 : okay i think that's it
• 08:04 : now i'm gonna verify this answer
• 08:07 : by um by running through this algorithm
• 08:11 : by hand okay
• 08:15 : let's use um use the
• 08:20 : input examples that we're given so
• 08:23 : the x is 2
• 08:27 : and the n is
• 08:30 : 10. i'm going to use a program counter
• 08:33 : here
• 08:33 : which is going to be
• 08:37 : this cap here so here we've initialized
• 08:41 : xq2 and n210 here
• 08:44 : i'm going to advance the program counter
• 08:48 : and execute this statement which is
• 08:50 : going to set the product
• 08:53 : two one and then we're going to advance
• 08:56 : again
• 08:57 : uh this says i'm going to create a base
• 09:00 : variable and set its value to
• 09:02 : whatever x has which is 2.
• 09:06 : i'm going to do an if statement if n is
• 09:09 : less than zero
• 09:10 : which is not true so we're skipping this
• 09:12 : next one and we're gonna go
• 09:14 : uh for i in range of n
• 09:18 : um now because this is a loop
• 09:22 : and there's actually some associated
• 09:25 : state
• 09:26 : i'm going to actually
• 09:29 : write out what the range of n would be
• 09:34 : the range of n i believe is gonna be an
• 09:37 : array
• 09:39 : that has as many items as
• 09:42 : n it's gonna start at zero
• 10:05 : okay and then i is gonna be one of these
• 10:09 : guys
• 10:09 : so i'm gonna actually put a little
• 10:14 : um maybe i need another little pointer
• 10:17 : here
• 10:18 : to remember where what i is
• 10:23 : okay so i initially
• 10:28 : is gonna be whatever this cap is
• 10:31 : pointing to
• 10:32 : is going to be zero
• 10:35 : and then we're going to advance into the
• 10:37 : loop of
• 10:38 : the body of the loop which says we're
• 10:41 : going to
• 10:41 : take the product multiply it by base and
• 10:44 : then
• 10:45 : set it back uh store it back into the
• 10:48 : variable product
• 10:50 : product is one one times
• 10:53 : base uh one times base is two so one
• 10:56 : times
• 10:57 : two is two we're going to take two and
• 10:59 : set it back
• 11:01 : into the product
• 11:09 : okay now i'm going back to the top of
• 11:10 : the loop i'm gonna move this pointer
• 11:13 : over
• 11:14 : and then that that is now gonna be the
• 11:17 : new version of
• 11:18 : i
• 11:21 : uh this is sliding down on me so i
• 11:25 : is one now i doesn't matter we're
• 11:29 : actually not
• 11:30 : using i'm not even using i
• 11:34 : so i might just not bother
• 11:38 : updating this i that's what i'm thinking
• 11:41 : because it's irrelevant um
• 11:44 : it's not getting referenced by the
• 11:46 : program
• 11:48 : um i'm just gonna have this pointer here
• 11:51 : okay so we're gonna do again product
• 11:53 : equals product times base so product is
• 11:56 : two bases two
• 11:58 : two times two is going to be four four
• 12:01 : storing four back into the product
• 12:06 : so four
• 12:09 : okay uh now moving this pointer over
• 12:13 : by another one and now we're gonna do it
• 12:16 : again
• 12:16 : four times two store it back two
• 12:19 : products four times two is
• 12:20 : eight we're gonna
• 12:24 : move this over one more time maybe i do
• 12:26 : it here
• 12:28 : so it won't drop
• 12:31 : uh okay we do this again product time
• 12:34 : space
• 12:35 : 8 times 2 is going to be 16
• 12:43 : 16 okay
• 12:46 : move this over again
• 12:50 : do the same thing 16 times 2 34.
• 13:00 : at 32 sorry
• 13:04 : uh okay
• 13:08 : i'll move this over one more um
• 13:12 : so 32 times two now is 64.
• 13:22 : move over one more 64 times two
• 13:25 : is going to be 128
• 13:35 : okay move it over one more 128 times two
• 13:39 : is going to
• 13:39 : be 256
• 13:48 : 256 okay move it over another one
• 13:52 : 256 times 2 is going to be 5 12
• 14:01 : and then move it finally
• 14:05 : this one one more time 2 times 5
• 14:08 : 12 is going to be 10 24.
• 14:14 : and then we're at the end of the range
• 14:16 : so we jump
• 14:17 : to the jump out of the for loop and
• 14:20 : we're going to return the product
• 14:22 : which is 1024. so return
• 14:25 : value
• 14:28 : is 10 24. uh that is the exact
• 14:33 : the expected output so we're good here
• 14:35 : for example number one
• 14:37 : let's go to example number two
• 14:40 : so our x again oh x is going to be 2.1
• 14:47 : n is going to be three okay
• 14:51 : all right we're initializing the product
• 14:55 : to one and then we're going to
• 14:58 : set the base to be
• 15:01 : x which is 2.1 and then if
• 15:05 : n is less than 0 which it's not
• 15:09 : so we're skipping the next statement
• 15:12 : and going to the for loop and for the
• 15:14 : for loop again
• 15:15 : we're going to generate a range range of
• 15:19 : n i'm going to write it out a range of n
• 15:22 : is a range of 3.
• 15:25 : so range of three is gonna have zero one
• 15:28 : and two in it
• 15:32 : and again let's have this little pointer
• 15:35 : here
• 15:36 : that remembers where in the iteration we
• 15:39 : are
• 15:40 : now we're going to do this statement
• 15:41 : product equals product
• 15:44 : times base so product 1
• 15:47 : times base is 2.1 gets us 2.1 we're
• 15:50 : going to store
• 15:52 : 2.1
• 15:54 : back into the product and go back to the
• 15:58 : top of
• 15:58 : four to move this pointer over by one
• 16:01 : now we're gonna do this line again
• 16:03 : product time space two point one
• 16:05 : times two point one what is 2.1 times
• 16:08 : 2.1
• 16:12 : let me see if i still remember how to do
• 16:15 : multiplication
• 16:17 : so i think it's
• 16:20 : i put a zero here
• 16:24 : oh not yet not yet let's do
• 16:28 : one times two point one
• 16:32 : one times two point one is two point one
• 16:37 : and then we're going to put a 0 here and
• 16:39 : do 2 times 2.1
• 16:41 : which is 4
• 16:44 : 2 and then we're going to add them
• 16:46 : together
• 16:47 : 1 4 four where should the decimal go
• 16:52 : i think the decimal should go here so we
• 16:55 : should have gotten
• 16:58 : 4.41
• 17:01 : i hope i'm right about that
• 17:08 : i'm going to move the pointer over one
• 17:10 : more time
• 17:12 : and then we're going to do the same
• 17:13 : thing again this time we're going to do
• 17:15 : 4.41 times
• 17:18 : 2.1
• 17:22 : um okay
• 17:25 : actually i think we line them up
• 17:31 : actually i i really don't remember how
• 17:34 : to do this
• 17:34 : but i'm going to try my best um
• 17:38 : 4.41
• 17:41 : and then 2 i'm going to put a 0 here and
• 17:44 : put 2
• 17:45 : times 4 4 1 which
• 17:48 : is going to get us 8 8
• 17:51 : 2. i'm going to add these digits
• 17:53 : together
• 17:56 : this is 12 with a carry and there's
• 17:59 : nine nine two six one and where should
• 18:01 : the decimal go
• 18:02 : i believe it should go
• 18:04 : [Music]
• 18:06 : three because you can't add the the
• 18:09 : places
• 18:09 : of both from three so enter nine
• 18:13 : two six one that's what it does the
• 18:16 : expected answer so i think i got it
• 18:19 : right
• 18:24 : nine point two six one
• 18:29 : okay so oh where were at the end
• 18:33 : of the range so that's going to drop out
• 18:36 : of the forum and return the product
• 18:38 : which is
• 18:39 : the right answer okay finally
• 18:45 : let's do the last one which has input of
• 18:49 : x is two and n is
• 18:52 : negative two this is the one that's
• 18:55 : gonna exercise
• 18:56 : this if statement see if that works
• 19:00 : um okay so we're gonna initialize the
• 19:03 : product
• 19:06 : to one initialize the base
• 19:10 : to whatever x is which is two
• 19:13 : if n is less than one which is this
• 19:16 : in this case then we're going to change
• 19:18 : the base to one
• 19:20 : divided by two so 1 divided by
• 19:24 : 2 is 0.5
• 19:30 : and then now we're gonna do this for
• 19:31 : loop
• 19:33 : um
• 19:37 : ah there's a mistake because
• 19:40 : this range of n is going to be range of
• 19:45 : range of negative 2 and i don't think
• 19:47 : that's what i want
• 19:48 : i think i need to do an absolute value
• 19:52 : of n here
• 19:55 : so i'm going to go ahead and do that
• 20:09 : okay this is called just in time
• 20:13 : coding you while the computer is
• 20:17 : executing in the code you see a mistake
• 20:20 : in the code
• 20:20 : you fix it just in time before the
• 20:23 : computer executes
• 20:25 : anyway so now that with this
• 20:29 : absolute value in in in place we're
• 20:34 : gonna end up doing a range of
• 20:35 : two which is gonna give us the array
• 20:40 : or list as we say in python that has the
• 20:44 : number
• 20:44 : zero and one and we're gonna have a
• 20:46 : pointer here
• 20:48 : okay so now we're gonna do product times
• 20:53 : the base and store it back in the
• 20:56 : product so
• 20:57 : that's gonna give us a 0.5
• 21:02 : i'm going to move this pointer over and
• 21:05 : then do the same thing again
• 21:07 : here 0.5 times 0.5
• 21:10 : pretty sure that's 0.25
• 21:14 : but i will do it out just in case
• 21:19 : so 5 times 5 is 25
• 21:22 : and we have to shift the decimal point
• 21:26 : over two places because there are two
• 21:28 : places
• 21:29 : combined so 0.25
• 21:34 : is the product
• 21:41 : and then this is the end of the range so
• 21:43 : we're going to jump out of this four
• 21:45 : loop and return the product
• 21:47 : so return value is 0.25
• 21:51 : and that is the expected answer very
• 21:54 : good so
• 21:55 : i'm gonna go ahead and type this
• 21:58 : solution
• 21:59 : product 1 base equal x
• 22:02 : if n is less than 0 base
• 22:06 : is 1 divided by x
• 22:09 : i in range of absolute value of
• 22:13 : n products
• 22:17 : times base product
• 22:22 : let's try to run this code
• 22:26 : it likes it i'm gonna do a submit
• 22:30 : time limit exceeded
• 22:41 : you