algorithm/Week_01/id_26/Leetcode_50_26.java at master · feixiangcode/algorithm · GitHub

History

106 lines (90 loc) · 2.62 KB

Raw

100

101

102

103

104

105

106

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

// Id : 50

// Author : Fanlu Hai

// Date : 2018-04-17

public class PowXN {

//Time Limit Exceeded, this should be O(n) which means I need O(log(n)) or better.

public double myPowVerySlow(double x, int n) {

double result = x;

if (n == 0) {

return 1;

}

if (n > 0) {

for (int i = 1; i < n; i++) {

result *= x;

}

return result;

}

n = -n;

for (int i = 1; i < n; i++) {

result *= x;

}

return 1 / result;

}

// x pow of n usually means you need to multiple x for n times, we can use dichotomy to reduce it.

public double myPowWithOverflowProblem(double x, int n) {

if (n == 0) {

return 1;

}

if (n < 0) {

//! here is the problem, -2147483648 will cause int overflow as it can't be bigger than 2147483647

n = -n;

x = 1 / x;

}

double result = 1;

double tmp = x;

while (true) {

if (n == 1) {

return result * tmp;

}

if (n % 2 == 1) {

result *= tmp;

}

n /= 2;

tmp *= tmp;

}

// x pow of n usually means you need to multiple x for n times, we can use dichotomy to reduce it.

// solved int overflow problem

// did not use recursion

// 82.1 100%

public double myPow(double x, int n) {

boolean minValue = false;

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

return 1;

}

// handle -2147483648 in a not very clean way

if (n == Integer.MIN_VALUE) {

n++;

minValue = true;

}

if (n < 0) {

n = -n;

x = 1 / x;

}

double result = 1;

double tmp = x;

while (true) {

if (n == 1) {

if (minValue)

return result * tmp * x;

return result * tmp;

}

if (n % 2 == 1) {

result *= tmp;

}

n /= 2;

tmp *= tmp;

}

public static void main(String[] args) {

PowXN powXN = new PowXN();

System.out.println(powXN.myPow(2, 11));

System.out.println(powXN.myPow(2, 12));

System.out.println(powXN.myPow(5, -2));

System.out.println(powXN.myPow(8, 4));

System.out.println(powXN.myPow(0.9, 2147483647));

System.out.println(powXN.myPow(1, -2147483647));

System.out.println(powXN.myPow(0.3, -2147483648));

}

algorithm/Week_01/id_26/Leetcode_50_26.java at master · feixiangcode/algorithm · GitHub

Expand file tree

Breadcrumbs

Leetcode_50_26.java

Latest commit

History

Breadcrumbs

Leetcode_50_26.java

File metadata and controls