find-products-of-elements-of-big-array

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

<table border="1">
	<tbody>
		<tr>
			<th>num</th>
			<th>Binary Representation</th>
			<th>powerful array</th>
		</tr>
		<tr>
			<td>1</td>
			<td>00001</td>
			<td>[1]</td>
		</tr>
		<tr>
			<td>8</td>
			<td>01000</td>
			<td>[8]</td>
		</tr>
		<tr>
			<td>10</td>
			<td>01010</td>
			<td>[2, 8]</td>
		</tr>
		<tr>
			<td>13</td>
			<td>01101</td>
			<td>[1, 4, 8]</td>
		</tr>
		<tr>
			<td>23</td>
			<td>10111</td>
			<td>[1, 2, 4, 16]</td>
		</tr>
	</tbody>
</table>

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

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

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

&nbsp;
Example 1:

<div class="example-block">
Input: queries = [[1,3,7]]

Output: [4]

Explanation:

There is one query.

<code>big_nums[1..3] = [2,1,2]</code>. The product of them is 4. The result is <code>4 % 7 = 4.</code>
</div>

Example 2:

<div class="example-block">
Input: queries = [[2,5,3],[7,7,4]]

Output: [2,2]

Explanation:

There are two queries.

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

Second query: <code>big_nums[7] = 2</code>. The result is <code>2 % 4 = 2</code>.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= queries.length &lt;= 500</code></li>
	<li><code>queries[i].length == 3</code></li>
	<li><code>0 &lt;= queries[i][0] &lt;= queries[i][1] &lt;= 1015</code></li>
	<li><code>1 &lt;= queries[i][2] &lt;= 105</code></li>
</ul>

findProductsOfElements

Find Products of Elements of Big Array

Bit Manipulation

Array

Binary Search

一个非负整数 <code>x</code>&nbsp;的 强数组&nbsp;指的是满足元素为 2 的幂且元素总和为 <code>x</code> 的最短有序数组。下表说明了如何确定 强数组 的示例。可以证明，<code>x</code>&nbsp;对应的强数组是独一无二的。

<table border="1">
	<tbody>
		<tr>
			<th>数字</th>
			<th>二进制表示</th>
			<th>强数组</th>
		</tr>
		<tr>
			<td>1</td>
			<td>00001</td>
			<td>[1]</td>
		</tr>
		<tr>
			<td>8</td>
			<td>01000</td>
			<td>[8]</td>
		</tr>
		<tr>
			<td>10</td>
			<td>01010</td>
			<td>[2, 8]</td>
		</tr>
		<tr>
			<td>13</td>
			<td>01101</td>
			<td>[1, 4, 8]</td>
		</tr>
		<tr>
			<td>23</td>
			<td>10111</td>
			<td>[1, 2, 4, 16]</td>
		</tr>
	</tbody>
</table>

&nbsp;

我们将每一个升序的正整数 <code>i</code>&nbsp;（即1，2，3等等）的 强数组&nbsp;连接得到数组&nbsp;<code>big_nums</code>&nbsp;，<code>big_nums</code>&nbsp;开始部分为&nbsp;<code>[1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...]</code>&nbsp;。

给你一个二维整数数组&nbsp;<code>queries</code>&nbsp;，其中&nbsp;<code>queries[i] = [fromi, toi, modi]</code>&nbsp;，你需要计算&nbsp;<code>(big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) % modi</code>&nbsp;。

请你返回一个整数数组&nbsp;<code>answer</code>&nbsp;，其中&nbsp;<code>answer[i]</code>&nbsp;是第 <code>i</code>&nbsp;个查询的答案。

&nbsp;

示例 1：

输入：queries = [[1,3,7]]

输出：[4]

解释：

只有一个查询。

<code>big_nums[1..3] = [2,1,2]</code>&nbsp;。它们的乘积为 4。结果为&nbsp;<code>4 % 7 = 4</code>。

示例 2：

输入：queries = [[2,5,3],[7,7,4]]

输出：[2,2]

解释：

有两个查询。

第一个查询：<code>big_nums[2..5] = [1,2,4,1]</code>&nbsp;。它们的乘积为 8 。结果为&nbsp; <code>8 % 3 = 2</code>。

第二个查询：<code>big_nums[7] = 2</code>&nbsp;。结果为 <code>2 % 4 = 2</code>。

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= queries.length &lt;= 500</code></li>
	<li><code>queries[i].length == 3</code></li>
	<li><code>0 &lt;= queries[i][0] &lt;= queries[i][1] &lt;= 1015</code></li>
	<li><code>1 &lt;= queries[i][2] &lt;= 105</code></li>
</ul>

&nbsp;

数字	二进制表示	强数组
1	00001	[1]
8	01000	[8]
10	01010	[2, 8]
13	01101	[1, 4, 8]
23	10111	[1, 2, 4, 16]