[JAVA 문제 풀이] 415. Range Product Queries of Powers

Range Product Queries of Powers - LeetCode

Can you solve this real interview question? Range Product Queries of Powers - Given a positive integer n, there exists a 0-indexed array called powers, composed of the minimum number of powers of 2 that sum to n. The array is sorted in non-decreasing order, and there is only one way to form the array. You are also given a 0-indexed 2D integer array queries, where queries[i] = [lefti, righti]. Each queries[i] represents a query where you have to find the product of all powers[j] with lefti <= j <= righti. Return an array answers, equal in length to queries, where answers[i] is the answer to the ith query. Since the answer to the ith query may be too large, each answers[i] should be returned modulo 109 + 7.   Example 1: Input: n = 15, queries = [[0,1],[2,2],[0,3]] Output: [2,4,64] Explanation: For n = 15, powers = [1,2,4,8]. It can be shown that powers cannot be a smaller size. Answer to 1st query: powers[0] * powers[1] = 1 * 2 = 2. Answer to 2nd query: powers[2] = 4. Answer to 3rd query: powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64. Each answer modulo 109 + 7 yields the same answer, so [2,4,64] is returned. Example 2: Input: n = 2, queries = [[0,0]] Output: [2] Explanation: For n = 2, powers = [2]. The answer to the only query is powers[0] = 2. The answer modulo 109 + 7 is the same, so [2] is returned.   Constraints: * 1 <= n <= 109 * 1 <= queries.length <= 105 * 0 <= starti <= endi < powers.length

https://leetcode.com/problems/range-product-queries-of-powers/description/

양의 정수 'n'이 주어지면 '멱'이라는 0-인덱스 배열이 존재하며,
이는 'n'에 합해지는 2의 최소 거듭제곱 수로 구성됩니다.
배열은 감소하지 않는 순서로 정렬되며 배열을 형성하는 방법은 하나뿐입니다.

또한 0-indexed 2D 정수 배열 'queries'가 주어지는데,
여기서 'queries[i] = [lefti, righti]'입니다.
각 'queries[i]'는 'lefti <= j <= righti'인
모든 '멱급수[j]'의 곱을 찾아야 하는 쿼리를 나타냅니다.

배열 '답변'을 'query'와 같은 길이로 반환합니다.
여기서 '답변'은 'i번째' 쿼리에 대한 답입니다. i번째 쿼리에 대한 답이 너무 클 수 있으므로
각 '답변'은 모듈로 '10^9 + 7'로 반환해야 합니다.

제약사항:

* 1 <= n <= 109
* 1 <= queries.length <= 105
* 0 <= starti <= endi < powers.length

내가 작성한 코드

import java.util.*;

class Solution {
    public int[] productQueries(int n, int[][] queries) {
        int power = 1; // 현재 확인 중인 2의 거듭제곱 값
        int MOD = 1_000_000_007; // 모듈러 값 (10^9 + 7)

        // power를 n보다 큰 최소 2의 거듭제곱으로 만들기
        while (power <= n) { 
            power *= 2;
        }

        power /= 2; // power를 n 이하인 최대 2의 거듭제곱으로 되돌림

        List<Integer> powers = new ArrayList<>(); // n을 구성하는 2의 거듭제곱들을 저장

        // n을 2의 거듭제곱 합으로 분해
        while (n > 0) {
            if (power <= n) { // 현재 power가 n보다 작거나 같으면
                powers.add(power); // powers에 추가
                n -= power; // n에서 해당 값 빼기
            }

            power /= 2; // 다음 작은 2의 거듭제곱으로 이동
        }

        int len = powers.size();
        int[][] prefix = new int[len][len]; // prefix[i][j]: powers[i]~powers[j] 구간 곱

        // prefix 배열 채우기
        for (int i = 0; i < len; i++) {
            prefix[i][i] = powers.get(len - 1 - i); // 단일 원소 (역순으로 접근)

            for (int j = i + 1; j < len; j++) {
                // 이전 값(prefix[i][j-1]) * 현재 원소(powers[n-1-j]) % MOD
                prefix[i][j] = (int) ((1L * prefix[i][j - 1] * powers.get(len - 1 - j)) % MOD);
            }
        }

        int[] res = new int[queries.length]; // 쿼리 결과 저장

        // queries 처리
        for (int i = 0; i < queries.length; i++) {
            res[i] = prefix[queries[i][0]][queries[i][1]]; // 미리 계산된 prefix 값 사용
        }

        return res;
    }
}