3145. Find Products of Elements of Big Array

Description

The powerful array of a non-negative integer x is defined as the shortest sorted array of powers of two that sum up to x. The table below illustrates examples of how the powerful array is determined. It can be proven that the powerful array of x is unique.

num	Binary Representation	powerful array
1	00001	[1]
8	01000	[8]
10	01010	[2, 8]
13	01101	[1, 4, 8]
23	10111	[1, 2, 4, 16]

The array big_nums is created by concatenating the powerful arrays for every positive integer i in ascending order: 1, 2, 3, and so on. Thus, big_nums begins as [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...].

You are given a 2D integer matrix queries, where for queries[i] = [fromi, toi, modi] you should calculate (big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) % modi.

Return an integer array answer such that answer[i] is the answer to the ith query.

 

Example 1:

Input: queries = [[1,3,7]]

Output: [4]

Explanation:

There is one query.

big_nums[1..3] = [2,1,2]. The product of them is 4. The result is 4 % 7 = 4.

Example 2:

Input: queries = [[2,5,3],[7,7,4]]

Output: [2,2]

Explanation:

There are two queries.

First query: big_nums[2..5] = [1,2,4,1]. The product of them is 8. The result is 8 % 3 = 2.

Second query: big_nums[7] = 2. The result is 2 % 4 = 2.

 

Constraints:

• 1 <= queries.length <= 500
• queries[i].length == 3
• 0 <= queries[i][0] <= queries[i][1] <= 1015
• 1 <= queries[i][2] <= 105

 

Solutions

Solution: Binary Search + Bit Manipulation

• Time complexity: O(nlog²Max(to))
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[][]} queries
 * @return {number[]}
 */
const findProductsOfElements = function (queries) {
  return queries.map(([from, to, mod]) => {
    const bigForm = BigInt(from);
    const bigTo = BigInt(to);
    const bigMod = BigInt(mod);
    const powers = getSumPowersK(bigTo + 1n) - getSumPowersK(bigForm);

    return Number(modPow(2n, powers, bigMod));
  });
};

function getSumPowers(num) {
  const len = BigInt(num.toString(2).length);
  let sum = 0n;
  let powerTwo = 1n;

  for (let bit = 0n; bit < len; bit++) {
    const base = powerTwo * 2n;
    const others = (num % base) + 1n - powerTwo;

    sum += (num / base) * powerTwo * bit;

    if (others > 0n) {
      sum += others * bit;
    }

    powerTwo *= 2n;
  }

  return sum;
}

function getSumBits(num) {
  let bits = 0n;

  for (let powerTwo = 1n; powerTwo <= num; powerTwo *= 2n) {
    const base = powerTwo * 2n;
    const others = (num % base) + 1n - powerTwo;

    bits += (num / base) * powerTwo;

    if (others > 0n) {
      bits += others;
    }
  }

  return bits;
}

function findFirstGreaterEqualSumBits(k) {
  let left = 1n;
  let right = k;

  while (left <= right) {
    const mid = (left + right) / 2n;

    getSumBits(mid) >= k ? (right = mid - 1n) : (left = mid + 1n);
  }

  return left;
}

function getSumPowersK(k) {
  const num = findFirstGreaterEqualSumBits(k);
  const len = BigInt(num.toString(2).length);
  let sumPowers = getSumPowers(num - 1n);
  let remainBitCount = k - getSumBits(num - 1n);

  for (let bit = 0n; bit < len; bit++) {
    if ((num >> bit) & 1n) {
      sumPowers += bit;
      remainBitCount -= 1n;
    }

    if (!remainBitCount) return sumPowers;
  }

  return sumPowers;
}

function modPow(base, exp, mod) {
  if (mod === 1n) return 0n;

  let result = 1n;

  while (exp) {
    if (exp % 2n) {
      result = (result * base) % mod;
    }

    base = (base * base) % mod;
    exp /= 2n;
  }

  return result;
}