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

AVAILABLE EXERCISES:

Exercise 9

Bitwise operations (bit-ops)

Exercise 8

Frontend

Exercise 7

Data Structures

Exercise 6

SQL

Exercise 5

Coding skills

Exercise 4

Algorithmic skills

Exercise 3

2017 Contest

Exercise 2

2016 Contest

Exercise 1

2015 Contest

Recover a broken array using partial information in another array.

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

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.

Copyright 2009–2023 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).

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.

Copyright 2009–2023 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).

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.

Copyright 2009–2023 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:

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

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.

^{9}+7.

Write a function:

int solution(List<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).

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.

^{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).

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.

^{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).

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.

^{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).

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.

^{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).

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.

^{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).

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.

^{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).

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.

^{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).

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.

^{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).

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.

^{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).

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.

^{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).

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.

^{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).

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.

^{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).

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.

^{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).

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.