mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-09-05 15:31:43 +08:00
99 lines
5.1 KiB
HTML
99 lines
5.1 KiB
HTML
<p>You are given an array of <strong>positive</strong> integers <code>nums</code> and a <strong>positive</strong> integer <code>k</code>. You are also given a 2D array <code>queries</code>, where <code>queries[i] = [index<sub>i</sub>, value<sub>i</sub>, start<sub>i</sub>, x<sub>i</sub>]</code>.</p>
|
|
|
|
<p>You are allowed to perform an operation <strong>once</strong> on <code>nums</code>, where you can remove any <strong>suffix</strong> from <code>nums</code> such that <code>nums</code> remains <strong>non-empty</strong>.</p>
|
|
|
|
<p>The <strong>x-value</strong> of <code>nums</code> <strong>for a given</strong> <code>x</code> is defined as the number of ways to perform this operation so that the <strong>product</strong> of the remaining elements leaves a <em>remainder</em> of <code>x</code> <strong>modulo</strong> <code>k</code>.</p>
|
|
|
|
<p>For each query in <code>queries</code> you need to determine the <strong>x-value</strong> of <code>nums</code> for <code>x<sub>i</sub></code> after performing the following actions:</p>
|
|
|
|
<ul>
|
|
<li>Update <code>nums[index<sub>i</sub>]</code> to <code>value<sub>i</sub></code>. Only this step persists for the rest of the queries.</li>
|
|
<li><strong>Remove</strong> the prefix <code>nums[0..(start<sub>i</sub> - 1)]</code> (where <code>nums[0..(-1)]</code> will be used to represent the <strong>empty</strong> prefix).</li>
|
|
</ul>
|
|
|
|
<p>Return an array <code>result</code> of size <code>queries.length</code> where <code>result[i]</code> is the answer for the <code>i<sup>th</sup></code> query.</p>
|
|
|
|
<p>A <strong>prefix</strong> of an array is a <span data-keyword="subarray">subarray</span> that starts from the beginning of the array and extends to any point within it.</p>
|
|
|
|
<p>A <strong>suffix</strong> of an array is a <span data-keyword="subarray">subarray</span> that starts at any point within the array and extends to the end of the array.</p>
|
|
|
|
<p><strong>Note</strong> that the prefix and suffix to be chosen for the operation can be <strong>empty</strong>.</p>
|
|
|
|
<p><strong>Note</strong> that x-value has a <em>different</em> definition in this version.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,4,5], k = 3, queries = [[2,2,0,2],[3,3,3,0],[0,1,0,1]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">[2,2,2]</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<ul>
|
|
<li>For query 0, <code>nums</code> becomes <code>[1, 2, 2, 4, 5]</code>, and the empty prefix <strong>must</strong> be removed. The possible operations are:
|
|
|
|
<ul>
|
|
<li>Remove the suffix <code>[2, 4, 5]</code>. <code>nums</code> becomes <code>[1, 2]</code>.</li>
|
|
<li>Remove the empty suffix. <code>nums</code> becomes <code>[1, 2, 2, 4, 5]</code> with a product 80, which gives remainder 2 when divided by 3.</li>
|
|
</ul>
|
|
</li>
|
|
<li>For query 1, <code>nums</code> becomes <code>[1, 2, 2, 3, 5]</code>, and the prefix <code>[1, 2, 2]</code> <strong>must</strong> be removed. The possible operations are:
|
|
<ul>
|
|
<li>Remove the empty suffix. <code>nums</code> becomes <code>[3, 5]</code>.</li>
|
|
<li>Remove the suffix <code>[5]</code>. <code>nums</code> becomes <code>[3]</code>.</li>
|
|
</ul>
|
|
</li>
|
|
<li>For query 2, <code>nums</code> becomes <code>[1, 2, 2, 3, 5]</code>, and the empty prefix <strong>must</strong> be removed. The possible operations are:
|
|
<ul>
|
|
<li>Remove the suffix <code>[2, 2, 3, 5]</code>. <code>nums</code> becomes <code>[1]</code>.</li>
|
|
<li>Remove the suffix <code>[3, 5]</code>. <code>nums</code> becomes <code>[1, 2, 2]</code>.</li>
|
|
</ul>
|
|
</li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,4,8,16,32], k = 4, queries = [[0,2,0,2],[0,2,0,1]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">[1,0]</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<ul>
|
|
<li>For query 0, <code>nums</code> becomes <code>[2, 2, 4, 8, 16, 32]</code>. The only possible operation is:
|
|
|
|
<ul>
|
|
<li>Remove the suffix <code>[2, 4, 8, 16, 32]</code>.</li>
|
|
</ul>
|
|
</li>
|
|
<li>For query 1, <code>nums</code> becomes <code>[2, 2, 4, 8, 16, 32]</code>. There is no possible way to perform the operation.</li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 3:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,2,1,1], k = 2, queries = [[2,1,0,1]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">[5]</span></p>
|
|
</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= nums[i] <= 10<sup>9</sup></code></li>
|
|
<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>
|
|
<li><code>1 <= k <= 5</code></li>
|
|
<li><code>1 <= queries.length <= 2 * 10<sup>4</sup></code></li>
|
|
<li><code>queries[i] == [index<sub>i</sub>, value<sub>i</sub>, start<sub>i</sub>, x<sub>i</sub>]</code></li>
|
|
<li><code>0 <= index<sub>i</sub> <= nums.length - 1</code></li>
|
|
<li><code>1 <= value<sub>i</sub> <= 10<sup>9</sup></code></li>
|
|
<li><code>0 <= start<sub>i</sub> <= nums.length - 1</code></li>
|
|
<li><code>0 <= x<sub>i</sub> <= k - 1</code></li>
|
|
</ul>
|