The mystery of number idempotent and perfect square

️Part1. Idempotent ️

️2  The power of ️

Topic details

Give you an integer  n, Please judge whether the integer is  2  Power square . If it is , return  true ; otherwise , return  false . If there is an integer  x  bring  

 , Think  n  yes  2  Power square .

Example ：

Input ：n = 1
Output ：true
explain ：20 = 1
Input ：n = 16
Output ：true
explain ：24 = 16
Input ：n = 3
Output ：false


Tips ：

The range of is integer

The scope of the .

Their thinking

utilize

There is only one binary sequence of powers of

1

And greater than

0

The nature of , Convert this problem into finding binary

1

The number of , If

1

individual , Then the number is

The power of . Binary system 1 How to find the number of ： Refer to the history blog ：

The finger of the sword offer series —— The finger of the sword  Offer 15.  Binary 1 The number of （C Language ）

Method 1：

  With C Language as an example , The storage form of integer is 32 Bit binary sequence , Complement stored in memory , For positive integers , The binary original code is the same as the complement , For negative integers , The complement code is added on the basis of the inverse code obtained by subtracting the highest bit from the original code 1. The first thought is to judge whether each bit of the binary sequence of the input integer is 1. We can associate this binary sequence with

1

To perform bitwise operations , because

1

Only the last bit of a binary sequence is

1

, So if the last bit of this binary sequence is

1

Then return to

1

, Otherwise return to

0

. Then we can shift the binary sequence to the right , So you can discard the rightmost sequence , after 32 operations , We can judge how many of the whole binary sequence

1

.

Method 2：

  Suppose the integer entered is

n

, We might as well

n

And

n-1

To perform bitwise operations , Then you will find that the result of the operation is the same as n comparison , One is missing from the binary sequence

1

, Generally speaking , Every time such an operation is performed , Binary

1

Will reduce one , We can design the solution according to the characteristics of this operation . We can put every time

n&(n-1)

Save your results to

n

, until

n=0

. Calculate the number of operations , namely

1

The number of .

Both of the above two methods can find 1 Number of digits , This article takes

Method 2

.

Why?

There is only one binary sequence

1

？

Let the binary sequence of a number be , among

by

0

or

1

：

Then the corresponding decimal number

If a number is

The power of , be

There is and only one number in

Others are

. Promote it. , about 32 position ,64 So is binary .

Source code

Java

// Specific writing
class Solution {
 public boolean isPowerOfTwo(int n) {
 int count = 0;
 if (n < 0){
 return false;
 }
 while (n != 0){
 n &= n - 1;
 count++;
 }
 if(count == 1){
 return true;
 }
 else{
 return false;
 }
 }
}

// Abbreviated
class Solution {
 public boolean isPowerOfTwo(int n) {
 return n > 0 && ((n & (n - 1)) == 0);
 }
}


C

bool isPowerOfTwo(int n){
 return n > 0 && ((n & (n - 1)) == 0);
}


C++

class Solution {
public:
 bool isPowerOfTwo(int n) {
 return n > 0 && ((n & (n - 1)) == 0);
 }
};


️3  The power of ️

Topic details

Given an integer , Write a function to determine if it is  3  Power square . If it is , return  true ; otherwise , return  false . Integers  n  yes  3  To the power of ： There are integers  x  bring  

.

Example ：

Input ：n = 27
Output ：true
Input ：n = 45
Output ：false


Tips ：

The range of is integer

The scope of the .

Their thinking

If a number is

3

The power of , Then this number is divided by

3

, The first time it can't be divided , The divisor must be

1

. such as 9,9/3=3,3/3=1,

1

Can not be

3

Divide up , The divisor is

1

. If a number is not 3 The power of is always divided by

3

The first divisor that cannot be divided must not be

1

. Another way ,

3

The power of is determined by the factor

3

And

1

form , So keep dividing by

3

, The final number must be another factor

1

.

Source code

Java

class Solution {
 public boolean isPowerOfThree(int n) {
 if (n <= 0) {
 return false;
 }
 int m = n;
 while (m % 3 == 0) {
 m /= 3;
 }
 if (m == 1) {
 return true;
 }
 else {
 return false;
 }
 }
}


C

bool isPowerOfThree(int n){
 if (n <= 0) 
 {
 return 0;
 }
 int m = n;
 while(m % 3 == 0)
 {
 m /= 3;
 }
 if (m == 1) 
 {
 return true;
 }
 return false;
}


C++

class Solution {
public:
 bool isPowerOfThree(int n) {
 if (n <= 0) 
 {
 return 0;
 }
 int m = n;
 while(m % 3 == 0)
 {
 m /= 3;
 }
 if (m == 1) 
 {
 return true;
 }
 return false;
 }
};


️4  The power of ️

Topic details

Given an integer , Write a function to determine if it is  4  Power square . If it is , return  true ; otherwise , return  false . Integers  n  yes  4  To the power of ： There are integers  x  bring  

.

Example ：

Input ：n = 16
Output ：true
Input ：n = 5
Output ：false


Tips ：

The range of is integer

The scope of the .

Their thinking

One is greater than 0 Number of numbers , Only one binary bit of this number is 1 And the digital analog 3 As the result of the 1, Then the number is 4 The power of .

deduction ： By the binomial theorem ：

The coefficient of the last term

, therefore

.

4 The power of must also be 2 The power of , So it's binary with 2 There is only one power of 1, One number is 2 Power of, but not 4 The power of , By the binomial theorem , This digital analog 3 The result must be 2：

The coefficient of the last term

.x For even when , This number is both 2 So is the power of 4 The power of , here

,

obtain

.x In an odd number of , The number is 2 Power of, but not 4 The power of , here

,

obtain

. Plus 4 The sum of powers of 2 The power of is the same , There is only one in the binary sequence

1

, So we can conclude that ：

Source code

Java

class Solution {
 public boolean isPowerOfFour(int n) {
 return n > 0 && ((n &(n-1)) == 0) && n % 3 == 1;
 }
}


C

bool isPowerOfFour(int n){
 return n > 0 && ((n &(n-1)) == 0) && n % 3 == 1;
}


C++

class Solution {
public:
 bool isPowerOfFour(int n) {
 return n > 0 && ((n &(n-1)) == 0) && n % 3 == 1;
 }
};


️Part2. Complete square ️

️ Complete square ️

Topic details

Given a   Positive integer  num , Write a function , If  num  It's a complete square , Then return to  true , Otherwise return to  false . Advanced ： Don't   Use any built-in library functions , Such as  sqrt .

Example ：

Input ：num = 16
Output ：true
Input ：num = 14
Output ：false


Tips ：

Their thinking

Method 1： Violent traversal , Pay attention to overflow , Not recommended . Method 2：  utilize

Formula calculation . Method 3： Two points search , See code for details .

Source code

Method 1：Java

class Solution {
 public boolean isPerfectSquare(int num) {
 for (int i = 1; (long)(i * i) <= (long)num && i <= num / 2 + 1; i++) {
 if (i * i == num) {
 return true;
 }
 }
 return false;
 }
}


Method 2：C

bool isPerfectSquare(int num){
 int i = 1;
 long sum = 0;
 while (sum <= num) {
 if (sum == num) {
 return true;
 }
 sum += i;
 i += 2;
 }
 return false;
}


Method 3：Java

class Solution {
 public boolean isPerfectSquare(int num) {
 int left = 1;
 int right = num;
 while (left <= right) {
 int mid = left + (right - left) / 2;
 int div = num / mid;
 if (mid == div) {
 if (mid * div == num) {
 return true;
 }
 left = mid + 1;
 }else if (mid > div) {
 right = mid - 1;
 }else {
 left = mid + 1;
 }
 }
 return false;
 }
}


summary

• 
  
  There is only one binary sequence of powers of
  1
  And greater than
  0
  .

• 
  
  The power of is determined by the factor
  3
  And
  1
  form , So keep dividing by
  3
  , The final number must be another factor
  1
  .

• One is greater than
  0
  Number of numbers , Only one binary bit of this number is
  1
  And the digital analog
  3
  As the result of the
  1
  , Then the number is
  
  
  The power of .

• The formula for calculating the complete square number ：