This is the 22nd day of my participation in the August More Text Challenge

A number raised to an integer power

16. Value raised to an integer power

Implement POW (x,n), that is, compute x to the NTH power (that is, x to the n). Library functions should not be used and large numbers should not be considered.

Example 1:

Input: x = 2.00000, n = 10 Output: 1024.00000Copy the code

Example 2:

Input: x = 2.10000, n = 3 Output: 9.26100Copy the code

Example 3:

Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2^(-2) = (1/2)^2 = 1/4 = 0.25Copy the code

Answer key

Method a recursion

Using a recursive approach:

  • When n=0, any x returns 1
  • When n=1, return x
  • When n=-1, return 1/x

For other n values:

  • If n is even, myPow(x,n) = myPow(x,n/2)*myPow(x,n/2)
  • When n is odd, myPow (x, n) = myPow (x, (n – 1) / 2) * myPow (x, (n – 1) / 2) * x

Note: To recurse, first obtain myPow(x,n/2) with a variable and then square it to reduce the time complexity (reduce the number of recursive calls).

 / * * *@param {number} x
  * @param {number} n
  * @return {number}* /
 var myPow = function(x,n){
   if(n===0) return 1;
   if(n===1) return x;
   if(n===-1) return 1/x;
   if(n%2= = =0) {let a = myPow(x,n/2);
     return a*a;
   }
   else{
     let b = myPow(x,(n-1) /2);
     returnb*b*x; }}Copy the code

Method two quick powers

Let’s say x is equal to 3 and n is equal to 5. So the binary of 5 is: 101. So, 3 to the fifth power can be written as follows:

You multiply x by itself, and you multiply x by 2 every time. Corresponds to the binary of n.

For example, the process of the whole algorithm is as follows:

  • The result value result is initially 1
  • X starts with 3, and the rightmost binary bit of n is 1. The updated result is x * n
  • N to the right. X multiplies, x updates to 3 to the second power. Since the rightmost binary bit of n is 0, the result is not updated
  • N to the right. X multiplies, x updates to 3 to the fourth. The rightmost binary bit of n is 1, and the update result is x * result
  • The end of the
 / * * *@param {number} x
  * @param {number} n
  * @return {number}* /
 var myPow = function(x, n) {
     let reusult = 1.0;
     // If it's negative, 2^-2 can become (1/2) ^2
     if(n<0) {// Js is not divisible by default
         x = 1/x;
         n = -n;
     }
     while(n>0) {if(n&1) {// If the rightmost bit of n is 1, multiply the current x to result
             reusult*=x;
         }
         x*=x; // x multiplies
         //>> is a shift of signed numbers, >>> is a shift of unsigned numbers
         // The first of the following is false, and the remaining two are true
         // n = n>>1
         // n = Math.floor(n/2)
         n = n>>>1
     }
     return reusult;
 };
Copy the code

Prints n digits from 1 to the largest

17. Print n digits from 1 to maximum

Enter the number n to print out the largest n decimal digits in sequence. For example, if you type 3, you print 1, 2, 3 up to 999.

Example 1:

Input: n = 1 Output: [1,2,3,4,5,6,7,8,9]Copy the code

Description:

  • Return a list of integers instead of printing
  • N is a positive integer

Answer key

Use built-in functions, which can be optimized using fast powers.

 / * * *@param {number} n
  * @return {number[]}* /
 var printNumbers = function(n){
   let max = ' '
   while(n--) max += '9'
   return new Array(max - '0').fill(0).map((val,index) = > index + 1)} orvar printNumbers = function(n) {
     let len = Math.pow(10, n)-1
     return Array.from({length: len}, (item, index) = > index+1)};Copy the code

Practice every day! The front end is a new one. I hope I can get a thumbs up