Problema: A non-empty zero-indexed array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + … + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + … + A[Q]) / (Q − P + 1). For example, array A such that: A[0] = 4 A[1] = 2 A[2] = 2 A[3] = 5 A[4] = 1 A[5] = 5 A[6] = 8 contains the[…]

Problema: A non-empty zero-indexed array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road. Array A contains only 0s and/or 1s: 0 represents a car traveling east, 1 represents a car traveling west. The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west. For example, consider array A such that: A[0] = 0 A[1] = 1 A[2] = 0 A[3] = 1 A[4] = 1 We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3),[…]

Problema: Write a function: def solution(A, B, K) that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.: { i : A ≤ i ≤ B, i mod K = 0 } For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10. Assume that: A and B are integers within the range [0..2,000,000,000]; K is an integer within the range [1..2,000,000,000]; A ≤ B. Complexity: expected worst-case time complexity is O(1); expected worst-case space complexity is O(1). Solución: Ok este problema esta fácil, lo[…]

Problema: You are given N counters, initially set to 0, and you have two possible operations on them: increase(X) − counter X is increased by 1, max counter − all counters are set to the maximum value of any counter. A non-empty zero-indexed array A of M integers is given. This array represents consecutive operations: if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X), if A[K] = N + 1 then operation K is max counter. For example, given integer N = 5 and array A such that: A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4the values of the counters[…]

Problema: Write a function: def solution(A) that, given a non-empty zero-indexed array A of N integers, returns the minimal positive integer (greater than 0) that does not occur in A. For example, given: A[0] = 1 A[1] = 3 A[2] = 6 A[3] = 4 A[4] = 1 A[5] = 2 the function should return 5. Assume that: N is an integer within the range [1..100,000]; each element of array A is an integer within the range [−2,147,483,648..2,147,483,647]. Complexity: expected worst-case time complexity is O(N); expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified. Solución: El problema nos dice que dado un array de N[…]

Hace poco empece a resolver los problemas de codility y al final de cada explicación del problema te ponen algo como esto: Complexity: expected worst-case time complexity is O(1); Ya había escuchado y leído un poco sobre Big O y entendía un poco a que se referían con O(n) pero nunca se me hizo útil ni tampoco le tome importancia. Hasta que me tope con varios problemas de codility que pedían O(1) y en mi resultado daba algo como “10% performance, O(n) detectado”, ahí fue cuando dije ah ok quieren O(1) y lo hice O(n) y ahora que hago? Antes que nada aclarar que esta no es una publicación donde veremos a fondo la definición teórica y matemática, es simplemente para[…]

Problema: A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river. You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds. The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X. You may assume that the speed of the current in the river[…]

Problema: A non-empty zero-indexed array A consisting of N integers is given. A permutation is a sequence containing each element from 1 to N once, and only once. For example, array A such that: A[0] = 4 A[1] = 1 A[2] = 3 A[3] = 2 is a permutation, but array A such that: A[0] = 4 A[1] = 1 A[2] = 3 is not a permutation, because value 2 is missing. The goal is to check whether array A is a permutation. Write a function: int solution(int A[], int N); that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not. For example, given array A such that: A[0] =[…]

Problema: A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape. Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], …, A[P − 1] and A[P], A[P + 1], …, A[N − 1]. The difference between the two parts is the value of: |(A[0] + A[1] + … + A[P − 1]) − (A[P] + A[P + 1] + … + A[N − 1])| In other words, it is the absolute difference between the sum of the first part and the sum of the second part. For example, consider array A such that: A[0] = 3 A[1] = 1 A[2] = 2[…]

Problema: A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing. Your goal is to find that missing element. Write a function: def solution(A) that, given a zero-indexed array A, returns the value of the missing element. For example, given array A such that: A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5 the function should return 4, as it is the missing element. Assume that: N is an integer within the range [0..100,000]; the elements of A are all distinct; each element of array A is an integer within the range [1..(N + 1)]. Complexity: expected worst-case[…]