ArrayRecovery coding task - Practice Coding

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

int solution(int B[], int N, int M);

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

int solution(vector<int> &B, int M);

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

int solution(vector<int> &B, int M);

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

class Solution { public int solution(int[] B, int M); }

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

int solution(List<int> B, int M);

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

func Solution(B []int, M int) int

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

class Solution { public int solution(int[] B, int M); }

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

class Solution { public int solution(int[] B, int M); }

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

function solution(B, M)

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Note: All arrays in this task are zero-indexed, unlike the common Lua convention. You can use #A to get the length of the array A.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

int solution(NSMutableArray *B, int M);

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

function solution(B: array of longint; N: longint; M: longint): longint;

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

function solution($B, $M);

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

sub solution { my ($B, $M) = @_; my @B = @$B; ... }

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

def solution(B, M)

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

def solution(b, m)

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

object Solution { def solution(b: Array[Int], m: Int): Int }

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

public func solution(_ B : inout [Int], _ M : Int) -> Int

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

Bob once had an array A with N elements. Each element was a positive integer not exceeding M.

Bob wrote a program to find an array B, defined as follows. For every index J, let's find the biggest index K such that K < J and A[K] < A[J]. Then set B[J] = A[K]. If there is no such index K, then set B[J] = 0. Intuitively, the J-th element of B contains the last value smaller than A[J] that appears before it, or 0 if there is no such element.

For example, let A = [2, 5, 3, 7, 9, 6]. Then B = [0, 2, 2, 3, 7, 3]. For instance, B[5] = 3, as A[5] is 6 and the last value before A[5] smaller than 6 is 3.

Bob computed an array B and then mistakenly deleted A. He now intends to find every valid array A from which his program would produce B. Count the number of such arrays A. Since the answer could be very big, return it modulo 10⁹+7.

Write a function:

Private Function solution(B As Integer(), M As Integer) As Integer

that, given an integer M and an array B with N integers, returns the remainder from the division by 10⁹+7 of the number of valid arrays A from which Bob would get B. You can assume that there is at least one such array.

For example, given: M = 4, B = [0, 2, 2] the function should return 3. The possible removed arrays A were [2, 3, 3], [2, 4, 3] and [2, 4, 4].

For the following data: M = 10, B = [0, 3, 5, 6] the function should return 4, as the possible arrays A were [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9] and [3, 5, 6, 10].

For the following data: M = 10⁵, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10⁵ and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10⁹+7).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [1..1,000,000,000];

each element of array B is an integer within the range [0..M];

there exists at least one valid array A from which Bob would get array B.

ArrayRecovery

Developer Training

Sign up for our newsletter:

Social: