Array
Simulation
Heap (Priority Queue)
Description
You are given an integer array nums
, an integer k
, and an integer multiplier
.
You need to perform k
operations on nums
. In each operation:
Find the minimum value x
in nums
. If there are multiple occurrences of the minimum value, select the one that appears first .
Replace the selected minimum value x
with x * multiplier
.
After the k
operations, apply modulo 109 + 7
to every value in nums
.
Return an integer array denoting the final state of nums
after performing all k
operations and then applying the modulo.
Example 1:
Input: nums = [2,1,3,5,6], k = 5, multiplier = 2
Output: [8,4,6,5,6]
Explanation:
Operation
Result
After operation 1
[2, 2, 3, 5, 6]
After operation 2
[4, 2, 3, 5, 6]
After operation 3
[4, 4, 3, 5, 6]
After operation 4
[4, 4, 6, 5, 6]
After operation 5
[8, 4, 6, 5, 6]
After applying modulo
[8, 4, 6, 5, 6]
Example 2:
Input: nums = [100000,2000], k = 2, multiplier = 1000000
Output: [999999307,999999993]
Explanation:
Operation
Result
After operation 1
[100000, 2000000000]
After operation 2
[100000000000, 2000000000]
After applying modulo
[999999307, 999999993]
Constraints:
1 <= nums.length <= 104
1 <= nums[i] <= 109
1 <= k <= 109
1 <= multiplier <= 106
Solutions
Solution 1: Priority Queue (Min-Heap) + Simulation
Let the length of the array $\textit{nums}$ be $n$, and the maximum value be $m$.
We first use a priority queue (min-heap) to simulate the operations until we complete $k$ operations or all elements in the heap are greater than or equal to $m$.
At this point, all elements in the array are less than $m \times \textit{multiplier}$. Since $1 \leq m \leq 10^9$ and $1 \leq \textit{multiplier} \leq 10^6$, $m \times \textit{multiplier} \leq 10^{15}$, which is within the range of a 64-bit integer.
Next, each operation will turn the smallest element in the array into the largest element. Therefore, after every $n$ consecutive operations, each element in the array will have undergone exactly one multiplication operation.
Thus, after the simulation, for the remaining $k$ operations, the smallest $k \bmod n$ elements in the array will undergo $\lfloor k / n \rfloor + 1$ multiplication operations, while the other elements will undergo $\lfloor k / n \rfloor$ multiplication operations.
Finally, we multiply each element in the array by the corresponding number of multiplication operations and take the result modulo $10^9 + 7$. This can be calculated using fast exponentiation.
The time complexity is $O(n \times \log n \times \log M + n \times \log k)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{nums}$, and $M$ is the maximum value in the array $\textit{nums}$.
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def getFinalState ( self , nums : List [ int ], k : int , multiplier : int ) -> List [ int ]:
if multiplier == 1 :
return nums
pq = [( x , i ) for i , x in enumerate ( nums )]
heapify ( pq )
m = max ( nums )
while k and pq [ 0 ][ 0 ] < m :
x , i = heappop ( pq )
heappush ( pq , ( x * multiplier , i ))
k -= 1
n = len ( nums )
mod = 10 ** 9 + 7
pq . sort ()
for i , ( x , j ) in enumerate ( pq ):
nums [ j ] = x * pow ( multiplier , k // n + int ( i < k % n ), mod ) % mod
return nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 class Solution {
public int [] getFinalState ( int [] nums , int k , int multiplier ) {
if ( multiplier == 1 ) {
return nums ;
}
PriorityQueue < long []> pq = new PriorityQueue <> (
( a , b ) -> a [ 0 ] == b [ 0 ] ? Long . compare ( a [ 1 ] , b [ 1 ] ) : Long . compare ( a [ 0 ] , b [ 0 ] ));
int n = nums . length ;
int m = Arrays . stream ( nums ). max (). getAsInt ();
for ( int i = 0 ; i < n ; ++ i ) {
pq . offer ( new long [] { nums [ i ] , i });
}
for (; k > 0 && pq . peek () [ 0 ] < m ; -- k ) {
long [] p = pq . poll ();
p [ 0 ] *= multiplier ;
pq . offer ( p );
}
final int mod = ( int ) 1e9 + 7 ;
for ( int i = 0 ; i < n ; ++ i ) {
long [] p = pq . poll ();
long x = p [ 0 ] ;
int j = ( int ) p [ 1 ] ;
nums [ j ] = ( int ) (( x % mod ) * qpow ( multiplier , k / n + ( i < k % n ? 1 : 0 ), mod ) % mod );
}
return nums ;
}
private int qpow ( long a , long n , long mod ) {
long ans = 1 % mod ;
for (; n > 0 ; n >>= 1 ) {
if (( n & 1 ) == 1 ) {
ans = ans * a % mod ;
}
a = a * a % mod ;
}
return ( int ) ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57 class Solution {
public :
vector < int > getFinalState ( vector < int >& nums , int k , int multiplier ) {
if ( multiplier == 1 ) {
return nums ;
}
using ll = long long ;
using pli = pair < ll , int > ;
auto cmp = []( const pli & a , const pli & b ) {
if ( a . first == b . first ) {
return a . second > b . second ;
}
return a . first > b . first ;
};
priority_queue < pli , vector < pli > , decltype ( cmp ) > pq ( cmp );
int n = nums . size ();
int m = * max_element ( nums . begin (), nums . end ());
for ( int i = 0 ; i < n ; ++ i ) {
pq . emplace ( nums [ i ], i );
}
while ( k > 0 && pq . top (). first < m ) {
auto p = pq . top ();
pq . pop ();
p . first *= multiplier ;
pq . emplace ( p );
-- k ;
}
auto qpow = [ & ]( ll a , ll n , ll mod ) {
ll ans = 1 % mod ;
a = a % mod ;
while ( n > 0 ) {
if ( n & 1 ) {
ans = ans * a % mod ;
}
a = a * a % mod ;
n >>= 1 ;
}
return ans ;
};
const int mod = 1e9 + 7 ;
for ( int i = 0 ; i < n ; ++ i ) {
auto p = pq . top ();
pq . pop ();
long long x = p . first ;
int j = p . second ;
nums [ j ] = static_cast < int > (( x % mod ) * qpow ( multiplier , k / n + ( i < k % n ? 1 : 0 ), mod ) % mod );
}
return nums ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 func getFinalState ( nums [] int , k int , multiplier int ) [] int {
if multiplier == 1 {
return nums
}
n := len ( nums )
pq := make ( hp , n )
for i , x := range nums {
pq [ i ] = pair { x , i }
}
heap . Init ( & pq )
m := slices . Max ( nums )
for ; k > 0 && pq [ 0 ]. x < m ; k -- {
x := pq [ 0 ]
heap . Pop ( & pq )
x . x *= multiplier
heap . Push ( & pq , x )
}
const mod int = 1e9 + 7
for i := range nums {
p := heap . Pop ( & pq ).( pair )
x , j := p . x , p . i
power := k / n
if i < k % n {
power ++
}
nums [ j ] = ( x % mod ) * qpow ( multiplier , power , mod ) % mod
}
return nums
}
func qpow ( a , n , mod int ) int {
ans := 1 % mod
a = a % mod
for n > 0 {
if n & 1 == 1 {
ans = ( ans * a ) % mod
}
a = ( a * a ) % mod
n >>= 1
}
return int ( ans )
}
type pair struct { x , i int }
type hp [] pair
func ( h hp ) Len () int { return len ( h ) }
func ( h hp ) Less ( i , j int ) bool { return h [ i ]. x < h [ j ]. x || h [ i ]. x == h [ j ]. x && h [ i ]. i < h [ j ]. i }
func ( h hp ) Swap ( i , j int ) { h [ i ], h [ j ] = h [ j ], h [ i ] }
func ( h * hp ) Push ( x any ) { * h = append ( * h , x .( pair )) }
func ( h * hp ) Pop () any { a := * h ; x := a [ len ( a ) - 1 ]; * h = a [: len ( a ) - 1 ]; return x }
GitHub