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

Count the minimum number of nails that allow a series of planks to be nailed.

Spoken language:

You are given two non-empty arrays A and B consisting of N integers. These arrays represent N planks. More precisely, A[K] is the start and B[K] the end of the K−th plank.

Next, you are given a non-empty array C consisting of M integers. This array represents M nails. More precisely, C[I] is the position where you can hammer in the I−th nail.

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

The goal is to find the minimum number of nails that must be used until all the planks are nailed. In other words, you should find a value J such that all planks will be nailed after using only the first J nails. More precisely, for every plank (A[K], B[K]) such that 0 ≤ K < N, there should exist a nail C[I] such that I < J and A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Thus, four is the minimum number of nails that, used sequentially, allow all the planks to be nailed.

Write a function:

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

that, given two non-empty arrays A and B consisting of N integers and a non-empty array C consisting of M integers, returns the minimum number of nails that, used sequentially, allow all the planks to be nailed.

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

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

You are given two non-empty arrays A and B consisting of N integers. These arrays represent N planks. More precisely, A[K] is the start and B[K] the end of the K−th plank.

Next, you are given a non-empty array C consisting of M integers. This array represents M nails. More precisely, C[I] is the position where you can hammer in the I−th nail.

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

The goal is to find the minimum number of nails that must be used until all the planks are nailed. In other words, you should find a value J such that all planks will be nailed after using only the first J nails. More precisely, for every plank (A[K], B[K]) such that 0 ≤ K < N, there should exist a nail C[I] such that I < J and A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Thus, four is the minimum number of nails that, used sequentially, allow all the planks to be nailed.

Write a function:

int solution(vector<int> &A, vector<int> &B, vector<int> &C);

that, given two non-empty arrays A and B consisting of N integers and a non-empty array C consisting of M integers, returns the minimum number of nails that, used sequentially, allow all the planks to be nailed.

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

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

You are given two non-empty arrays A and B consisting of N integers. These arrays represent N planks. More precisely, A[K] is the start and B[K] the end of the K−th plank.

Next, you are given a non-empty array C consisting of M integers. This array represents M nails. More precisely, C[I] is the position where you can hammer in the I−th nail.

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

The goal is to find the minimum number of nails that must be used until all the planks are nailed. In other words, you should find a value J such that all planks will be nailed after using only the first J nails. More precisely, for every plank (A[K], B[K]) such that 0 ≤ K < N, there should exist a nail C[I] such that I < J and A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Thus, four is the minimum number of nails that, used sequentially, allow all the planks to be nailed.

Write a function:

int solution(vector<int> &A, vector<int> &B, vector<int> &C);

that, given two non-empty arrays A and B consisting of N integers and a non-empty array C consisting of M integers, returns the minimum number of nails that, used sequentially, allow all the planks to be nailed.

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

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

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

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

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

int solution(List<int> A, List<int> B, List<int> C);

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

func Solution(A []int, B []int, C []int) int

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

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

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

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

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

function solution(A, B, C);

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

fun solution(A: IntArray, B: IntArray, C: IntArray): Int

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

function solution(A, B, C)

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

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.

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

int solution(NSMutableArray *A, NSMutableArray *B, NSMutableArray *C);

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

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

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

function solution($A, $B, $C);

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

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

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

def solution(A, B, C)

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

def solution(a, b, c)

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

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

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

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

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

function solution(A: number[], B: number[], C: number[]): number;

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

if we use the following nails:

- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.

Write a function:

Private Function solution(A As Integer(), B As Integer(), C As Integer()) As Integer

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

the function should return 4, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..
2*M];- A[K] ≤ B[K].