the physicists of a new world are working on an algorithm to create waves. An array can be represented as a wave if either of the following conditions is satisfied:
a1 > a2 and a2 < a3 and a3 > a4 and so on
a1 < a2 and a2 > a3 and a3 < a4 and so on
where a[i] is the element of the array.
Given an array arr of n integers, consisting of integers in the range 1 to m inclusive, or -1, find the number of ways to replace all the -1s in the array with an integer in the range 1 to m such that the resulting array can be represented as a wave. Since the answer can be large, compute it modulo 10^9 + 7
Example
Suppose n = 3, arr = [-1,3,-1], m =3
The possible ways to replace all the -1s in the array such that the resulting is a wave array are-
[1,3,2]
[1,3,1]
[2,3,1]
[2,3,2]
Hence the answer is 4
Function description:
Complete then function countWaysToCreateWave in the editor below.
countWaysToCreateWave have the following parameters:
arr[n]: an array of integers
m: an array
Returns
int: the number of ways to replace -1s in the array to make it a wave array, modulo 10^9+7
Code in C++
a1 > a2 and a2 < a3 and a3 > a4 and so on
a1 < a2 and a2 > a3 and a3 < a4 and so on
where a[i] is the element of the array.
Given an array arr of n integers, consisting of integers in the range 1 to m inclusive, or -1, find the number of ways to replace all the -1s in the array with an integer in the range 1 to m such that the resulting array can be represented as a wave. Since the answer can be large, compute it modulo 10^9 + 7
Example
Suppose n = 3, arr = [-1,3,-1], m =3
The possible ways to replace all the -1s in the array such that the resulting is a wave array are-
[1,3,2]
[1,3,1]
[2,3,1]
[2,3,2]
Hence the answer is 4
Function description:
Complete then function countWaysToCreateWave in the editor below.
countWaysToCreateWave have the following parameters:
arr[n]: an array of integers
m: an array
Returns
int: the number of ways to replace -1s in the array to make it a wave array, modulo 10^9+7
Code in C++
Add an Answer
More Questions From This User See All
Answers & Comments
Here's the Python function that implements the algorithm described to count the number of ways to replace the -1s in the array to create a wave array:
def countWaysToCreateWave(arr, m):
MOD = 10**9 + 7
n = len(arr)
def dp(idx, prev_val, prev_cmp):
if idx == n:
return 1
if dp_memo[idx][prev_val][prev_cmp] != -1:
return dp_memo[idx][prev_val][prev_cmp]
ans = 0
if arr[idx] == -1:
for x in range(1, m + 1):
if prev_cmp == 0 and x > prev_val:
ans = (ans + dp(idx + 1, x, 1)) % MOD
elif prev_cmp == 1 and x < prev_val:
ans = (ans + dp(idx + 1, x, 0)) % MOD
else:
x = arr[idx]
if prev_cmp == 0 and x > prev_val:
ans = (ans + dp(idx + 1, x, 1)) % MOD
elif prev_cmp == 1 and x < prev_val:
ans = (ans + dp(idx + 1, x, 0)) % MOD
dp_memo[idx][prev_val][prev_cmp] = ans
return ans
dp_memo = [[[-1] * 2 for _ in range(m + 1)] for _ in range(n + 1)]
result = dp(0, 0, 0)
return result
# Example usage
n = 3
arr = [-1, 3, -1]
m = 3
print(countWaysToCreateWave(arr, m)) # Output: 4
This function uses dynamic programming to calculate the number of ways to replace the -1s in the array to create a wave array while considering the modulo constraint.
#SPJ1