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

respectable

Count the distinct rectangle sizes, of area greater than or equal to X, that can be built out of a given set of segments.

Programming language:
Spoken language:

Halfling Woolly Proudhoof is an eminent sheep herder. He wants to build a pen (enclosure) for his new flock of sheep. The pen will be rectangular and built from exactly four pieces of fence (so, the pieces of fence forming the opposite sides of the pen must be of equal length). Woolly can choose these pieces out of N pieces of fence that are stored in his barn. To hold the entire flock, the area of the pen must be greater than or equal to a given threshold X.

Woolly is interested in the number of different ways in which he can build a pen. Pens are considered different if the sets of lengths of their sides are different. For example, a pen of size 1×4 is different from a pen of size 2×2 (although both have an area of 4), but pens of sizes 1×2 and 2×1 are considered the same.

Write a function:

int solution(int A[], int N, int X);

that, given an array A of N integers (containing the lengths of the available pieces of fence) and an integer X, returns the number of different ways of building a rectangular pen satisfying the above conditions. The function should return −1 if the result exceeds 1,000,000,000.

For example, given X = 5 and the following array A:

the function should return 2. The figure above shows available pieces of fence (on the left) and possible to build pens (on the right). The pens are of sizes 1x5 and 2x5. Pens of sizes 1×1 and 1×2 can be built, but are too small in area. It is not possible to build pens of sizes 2×3 or 3×5, as there is only one piece of fence of length 3.

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

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.

Halfling Woolly Proudhoof is an eminent sheep herder. He wants to build a pen (enclosure) for his new flock of sheep. The pen will be rectangular and built from exactly four pieces of fence (so, the pieces of fence forming the opposite sides of the pen must be of equal length). Woolly can choose these pieces out of N pieces of fence that are stored in his barn. To hold the entire flock, the area of the pen must be greater than or equal to a given threshold X.

Woolly is interested in the number of different ways in which he can build a pen. Pens are considered different if the sets of lengths of their sides are different. For example, a pen of size 1×4 is different from a pen of size 2×2 (although both have an area of 4), but pens of sizes 1×2 and 2×1 are considered the same.

Write a function:

int solution(vector<int> &A, int X);

that, given an array A of N integers (containing the lengths of the available pieces of fence) and an integer X, returns the number of different ways of building a rectangular pen satisfying the above conditions. The function should return −1 if the result exceeds 1,000,000,000.

For example, given X = 5 and the following array A:

the function should return 2. The figure above shows available pieces of fence (on the left) and possible to build pens (on the right). The pens are of sizes 1x5 and 2x5. Pens of sizes 1×1 and 1×2 can be built, but are too small in area. It is not possible to build pens of sizes 2×3 or 3×5, as there is only one piece of fence of length 3.

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

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.

Halfling Woolly Proudhoof is an eminent sheep herder. He wants to build a pen (enclosure) for his new flock of sheep. The pen will be rectangular and built from exactly four pieces of fence (so, the pieces of fence forming the opposite sides of the pen must be of equal length). Woolly can choose these pieces out of N pieces of fence that are stored in his barn. To hold the entire flock, the area of the pen must be greater than or equal to a given threshold X.

Woolly is interested in the number of different ways in which he can build a pen. Pens are considered different if the sets of lengths of their sides are different. For example, a pen of size 1×4 is different from a pen of size 2×2 (although both have an area of 4), but pens of sizes 1×2 and 2×1 are considered the same.

Write a function:

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

that, given an array A of N integers (containing the lengths of the available pieces of fence) and an integer X, returns the number of different ways of building a rectangular pen satisfying the above conditions. The function should return −1 if the result exceeds 1,000,000,000.

For example, given X = 5 and the following array A:

the function should return 2. The figure above shows available pieces of fence (on the left) and possible to build pens (on the right). The pens are of sizes 1x5 and 2x5. Pens of sizes 1×1 and 1×2 can be built, but are too small in area. It is not possible to build pens of sizes 2×3 or 3×5, as there is only one piece of fence of length 3.

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

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.

Write a function:

func Solution(A []int, X int) int

For example, given X = 5 and the following array A:

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

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

Write a function:

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

For example, given X = 5 and the following array A:

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

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

Write a function:

function solution(A, X);

For example, given X = 5 and the following array A:

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

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

Write a function:

function solution(A, X)

For example, given X = 5 and the following array A:

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

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.

Write a function:

int solution(NSMutableArray *A, int X);

For example, given X = 5 and the following array A:

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

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

Write a function:

function solution(A: array of longint; N: longint; X: longint): longint;

For example, given X = 5 and the following array A:

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

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

Write a function:

function solution($A, $X);

For example, given X = 5 and the following array A:

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

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

Write a function:

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

For example, given X = 5 and the following array A:

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

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

Write a function:

def solution(A, X)

For example, given X = 5 and the following array A:

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

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

Write a function:

def solution(a, x)

For example, given X = 5 and the following array A:

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

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

Write a function:

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

For example, given X = 5 and the following array A:

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

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

Write a function:

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

For example, given X = 5 and the following array A:

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

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

Write a function:

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

For example, given X = 5 and the following array A:

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

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

Write a function:

Private Function solution(A As Integer(), X As Integer) As Integer

For example, given X = 5 and the following array A:

Assume that:

- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].

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