FilesExpand file tree

 master

/

PowXn.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

98 lines (91 loc) · 1.83 KB

 master

/

PowXn.java

Copy path

Top

File metadata and controls

• Code
• Blame

98 lines (91 loc) · 1.83 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

// Source : https://leetcode.com/problems/powx-n/

// Author : Tianming Cao

// Date : 2018-02-11

/**********************************************************************************

*

* Implement pow(x, n).

*

* Example 1:

*

* Input: 2.00000, 10

* Output: 1024.00000

*

* Example 2:

*

* Input: 2.10000, 3

* Output: 9.26100

*

**********************************************************************************/

package powXn;

public class PowXn {

/**

* Divide-and-Conquer method

* For example:

*

* 3^9=(3^4)^2*3

* ↓

* 3^4=(3^2)^2

* ↓

* 3^2=3*3

* ↓

* 3=3

*

* So, both Space and Time are O(logN)

*/

public double recursion(double x, long n) {

if (n == 1) {

return x;

}

//We'd better use unsigned right shift

double half = recursion(x, n >>> 1);

if ((n & 1) == 0) {

return half * half;

} else {

return half * half * x;

}

}

public double myPow01(double x, int n) {

if (n == 0 || x == 1) {

return 1;

}

// Avoid being out of bounds, we should cast int to long

long m = n;

double result = recursion(x, Math.abs(m));

if (n > 0) {

return result;

} else {

return 1 / result;

}

}

public double myPow02(double x, int n) {

if (n == 0 || x == 1) {

return 1;

}

// Avoid being out of bounds, we should cast int to long

long m = n;

double result = bitFunction(x, Math.abs(m));

if (n > 0) {

return result;

} else {

return 1 / result;

}

}

/**

* Solution with bit-manipulation

* For example:

* 9=1001

* 3^9=(3^1)^1*(3^2)^0*(3^4)^0*(3^8)^1

* Space is O(1), Time is O(logN)

*/

public double bitFunction(double x, long n) {

double multy = 1;

double base = x;

for (long k = n; k >= 1; k >>>= 1) {

if ((k & 1) > 0) {

multy = multy * base;

}

base *= base;

}

return multy;

}

}