[LeetCode] 50. Pow(x, n) in O(log n) time

문제

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

**Binary Search의 예시 문제로 출제되었다.

 

예시

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

조건

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31-1 /* 이 조건이 끔찍한 오버플로우를 유발한다 */
• n is an integer.
• -10^4 <= x^n <= 10^4

초안

O(n) 시간 복잡도를 가지는 재귀문으로는 시간 초과가 뜨길래,

공간을 좀 희생해서 x^1, x^2, x^4... 를 저장한 배열을 만들고, n을 이진수로 만들어서 각 값을 더하기로 했다.

연산을 간단하게 하기 위해 x와 n은 우선 절대값으로 계산한 후 -1을 곱하거나 역수로 뒤집기로 했다.

근데 역수로 뒤집는 과정이 심각한 오버플로우를 유발했다.

그래서 powTable의 seed를 n의 부호에 따라서 다르게 넣어주는 것으로 해결했다.

 

교훈
: Int 오버플로우 범위인 2*10^9를 상식으로 외워두고 지금 하는 행동이 오버플로우를 일으킬지 아닐지 생각해보자.

import kotlin.math.absoluteValue

fun myPow(x: Double, n: Int): Double {
    return calculateSign(x < 0, n) * calculateAbsoluteValue(x.absoluteValue, n)
}

private fun calculateSign(isNegative: Boolean, n: Int): Double {
    return if (!isNegative) {
        1.0
    } else if (n % 2 == 0) {
        1.0
    } else {
        -1.0
    }
}

private fun calculateAbsoluteValue(absX: Double, n: Int): Double {
    // 예외처리
    if (absX == 1.0 || absX == 0.0) return absX
    if (n == 0) return 1.0

    // pre-processing : x^(2^i) 를 저장하는 테이블 만들기. O(log n) 소요
    val powTable = createPowTable(absX, n)

    // n을 binary로 변환한 다음에 table에서 더해서 반환하면 됨
    val binaryN = n.absoluteValue.toString(2).reversed()
    var result = 1.0
    for (i in binaryN.indices) {
        if (binaryN[i] == '1') {
            result *= powTable[i]
        }
    }

    return result
}

fun createPowTable(absX: Double, n: Int): ArrayList<Double> {
    val powTable = arrayListOf<Double>()
    var nCopy = n
    var index = 1
    if (n < 0){
        powTable.add(1/absX)
    } else {
        powTable.add(absX)
    }
    while (nCopy != 0){
        val square = powTable[index - 1] * powTable[index - 1]
        powTable.add(square)
        nCopy /= 2
        index++
    }
    return powTable
}

- Time Complexity

: O(log n)이다. powTable을 만드는 동작, 그리고 n의 이진수를 탐색하는 것 모두 O(log n)의 시간복잡도를 가지기 때문이다.

- Space Complexity

: O(log n)이다. powTable을 별도로 만들어야하기 때문.

 

개선할 점

- powTable을 생성하는 대신 재귀적으로 제곱을 수행하면 메모리를 아낄 수 있다.

- 정수 n을 이진문자열로 바꾸는 대신 shift 연산을 이용해도 좋다.

    var n = 123
    while (n > 1){
        println(n.toString(2))
        /* 둘은 동일한 결과를 내지만 bit operation이 더 빠르다 */
        // n = n shr 1
        // n /= 2
    }