Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

AVAILABLE LESSONS:

Lesson 1

Iterations

Lesson 2

Arrays

Lesson 3

Time Complexity

Lesson 4

Counting Elements

Lesson 5

Prefix Sums

Lesson 6

Sorting

Lesson 7

Stacks and Queues

Lesson 8

Leader

Lesson 9

Maximum slice problem

Lesson 10

Prime and composite numbers

Lesson 11

Sieve of Eratosthenes

Lesson 12

Euclidean algorithm

Lesson 13

Fibonacci numbers

Lesson 14

Binary search algorithm

Lesson 15

Caterpillar method

Lesson 16

Greedy algorithms

Lesson 17

Dynamic programming

Lesson 90

Tasks from Indeed Prime 2015 challenge

Lesson 91

Tasks from Indeed Prime 2016 challenge

Lesson 92

Tasks from Indeed Prime 2016 College Coders challenge

Lesson 99

Future training

ambitious

Recover a broken array using partial information in another array.

Programming language:
Spoken language:

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^{9}+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^{9}+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^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));
- expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

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^{9}+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^{9}+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^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));
- expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

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^{9}+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^{9}+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^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));
- expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

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

^{9}+7.

Write a function:

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

^{9}+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.

^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));

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

^{9}+7.

Write a function:

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

^{9}+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.

^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));

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

^{9}+7.

Write a function:

function solution(B, M)

^{9}+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.

^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));

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.

^{9}+7.

Write a function:

int solution(NSMutableArray *B, int M);

^{9}+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.

^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));

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

^{9}+7.

Write a function:

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

^{9}+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.

^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));

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

^{9}+7.

Write a function:

function solution($B, $M);

^{9}+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.

^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));

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

^{9}+7.

Write a function:

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

^{9}+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.

^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));

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

^{9}+7.

Write a function:

def solution(B, M)

^{9}+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.

^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));

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

^{9}+7.

Write a function:

def solution(b, m)

^{9}+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.

^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));

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

^{9}+7.

Write a function:

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

^{9}+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.

^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));

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

^{9}+7.

Write a function:

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

^{9}+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.

^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));

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

^{9}+7.

Write a function:

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

^{9}+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.

^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));

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

^{9}+7.

Write a function:

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

^{9}+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.

^{5}, B = [0, 0] there are 5000050000 possible arrays (the first element in array A can be anything in the range 1..10^{5} and the second element can be either equal or smaller), so the function should return 49965 (as we are taking modulo 10^{9}+7).

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N*log(N));

Information about upcoming challenges, solutions and lessons directly in your inbox.

© 2009–2018 Codility Ltd., registered in England and Wales (No. 7048726). VAT ID GB981191408. Registered office: 107 Cheapside, London EC2V 6DN