[LeetCode 2438] Range Product Queries of Powers

문제 바로가기

Description

---

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] = [left_i, right_i]. Each queries[i] represents a query where you have to find the product of all powers[j] with left_i <= j <= right_i.

Return an array answers, equal in length to queries, where answers[i] is the answer to the i^th query. Since the answer to the i^th query may be too large, each answers[i] should be returned modulo 10^9 + 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 10^9 + 7 is the same, so [2] is returned.

Constraints

---

• 1 <= n <= 10^9
• 1 <= queries.length <= 10^5
• 0 <= start_i <= end_i < powers.length

Hint

---

Hint 1

  The `powers` array can be created using the binary representation of `n`.
	

Hint 2

  Once `powers` is formed, the products can be taken using brute force.
	

Code

---

내 제출

---

class Solution {
    public int[] productQueries(int n, int[][] queries) {
        int[] powers = new int[Integer.bitCount(n)];
        for (int i = 0; n > 0; ++i) {
            int x = n & -n;
            powers[i] = x;
            n -= x;
        }
        int m = queries.length;
        int[] ans = new int[m];
        final int mod = (int) 1e9 + 7;
        for (int i = 0; i < m; ++i) {
            int l = queries[i][0], r = queries[i][1];
            long x = 1;
            for (int j = l; j <= r; ++j) {
                x = x * powers[j] % mod;
            }
            ans[i] = (int) x;
        }
        return ans;
    }
}

Runtime	Memory
15 ms	95.2 MB

다른 풀이

---

class Solution {
    static long st[];
    public int[] productQueries(int n, int[][] queries) {
        int prev=1;
        List<Integer> obj=new ArrayList<>();
        obj.add(prev);
      for(int i=0;i<n;i++)
      {
        if((prev*2)>n)break;
        obj.add(prev*2);
        prev=prev*2;
      }
      Set<Integer> obj2=new HashSet<>();
      
    List<Integer> lp=new ArrayList<>();
    for(int r=obj.size()-1;r>=0;r--)
    {
        if(n==0)break;
        if(n>=obj.get(r))
        {
            lp.add(obj.get(r));
            n=n-obj.get(r);
        }else
        {
            continue;
        }
    }
    st=new long[4*lp.size()];
    Collections.sort(lp);
    build(lp,st,0,lp.size()-1,1);
    

     int ans[]=new int[queries.length];
     int op=0;
     for(int it[]:queries)
     {
        int x=it[0];
        int y=it[1];
      long kp=  query(x,y,0,lp.size()-1,1);
      ans[op++]=(int)kp;
     }
     return ans;
    }
    public static long query(int x,int y,int l,int r,int node)
    {
        if(x>r || y<l)return 1;
        if(x<=l && y>=r)return st[node];
        int mid=(l+r)/2;
        return ((query(x,y,l,mid,2*node)%1000000007)*(query(x,y,mid+1,r,2*node+1)%1000000007))%1000000007;
    }
    public static void build(List<Integer> lp,long st[],int l,int r,int node)
{
    if(l==r)
    {
        st[node]=lp.get(l);
        return ;
    }
    int mid=(l+r)/2;
    build(lp,st,l,mid,2*node);
    build(lp,st,mid+1,r,2*node+1);
    st[node]=(((st[2*node])%1000000007)*((st[2*node+1])%1000000007))%1000000007;
}
   
    
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/2400-2499/2438.Range%20Product%20Queries%20of%20Powers/Solution.java