|
| 1 | +packageeasy; |
| 2 | +/**342. Power of Four QuestionEditorial Solution My Submissions |
| 3 | +Total Accepted: 31004 |
| 4 | +Total Submissions: 86897 |
| 5 | +Difficulty: Easy |
| 6 | +Given an integer (signed 32 bits), write a function to check whether it is a power of 4. |
| 7 | +
|
| 8 | +Example: |
| 9 | +Given num = 16, return true. Given num = 5, return false. |
| 10 | +
|
| 11 | +Follow up: Could you solve it without loops/recursion?*/ |
| 12 | +publicclassPowerOfFour { |
| 13 | +//with my original idea in the bottom, just dive a little bit deeper, you can realize that another important feature of a number |
| 14 | +//that is power of four is that its only single one bit must appear on the odd position, and power of two won't meet this requirement |
| 15 | +//decimal number 8 has binary format: 0000-0000-0000-0000-0000-0000-0000-1000 |
| 16 | +//decimal number 16 has binary format: 0000-0000-0000-0000-0000-0000-0001-0000 |
| 17 | +//hex number 0x55555555 has binary format: 1010-1010-1010-1010-1010-1010-1010-1010 |
| 18 | +//thus, doing AND with 0x55555 will check if the only one bit is located on the odd position, thus ruling out those that are power of 2 but not power of 4 |
| 19 | +publicbooleanisPowerOfFour_bit_manipulation(intnum){ |
| 20 | +return (num >0 &&1073741824%num ==0 && (num&0x55555555) !=0); |
| 21 | + } |
| 22 | + |
| 23 | +publicbooleanisPowerOfFour_base_conversion(intnum){ |
| 24 | +//^ means to match the beginning of a line |
| 25 | +//$ means to match the end of a line |
| 26 | +//* means zero or more of the preceding character |
| 27 | +returnInteger.toString(num,4).matches("^10*$"); |
| 28 | + } |
| 29 | + |
| 30 | +//a regular loop method to make it AC'ed |
| 31 | +publicbooleanisPowerOfFour(intnum){ |
| 32 | +if(num <4 &&num !=1)returnfalse; |
| 33 | +while(num !=1){ |
| 34 | +if(num %4 !=0)returnfalse; |
| 35 | +num /=4; |
| 36 | + } |
| 37 | +returntrue; |
| 38 | + } |
| 39 | + |
| 40 | +//simply using the max number possible that is power of 4 won't work for this case, because, that number is a power of 2, but might |
| 41 | +//not be a power of 4, e.g. number 8 |
| 42 | +publicbooleanisPowerOfFour_not_accepted(intnum) { |
| 43 | +return (num >3 &&1073741824 %num ==0); |
| 44 | + } |
| 45 | + |
| 46 | +publicstaticvoidmain(String...strings){ |
| 47 | +inttemp =4,maxPowerOf4 =4; |
| 48 | +while(temp >0){ |
| 49 | +temp *=4; |
| 50 | +if(temp >0)maxPowerOf4 =temp; |
| 51 | + } |
| 52 | +System.out.println("maxPowerOf4 is: " +maxPowerOf4); |
| 53 | + |
| 54 | + |
| 55 | +System.out.println(Integer.parseInt("55555555",16)); |
| 56 | +System.out.println(Integer.toBinaryString(Integer.parseInt("55555555",16))); |
| 57 | + } |
| 58 | +} |