Знайти помилку в коді

Є реалізація функції, яка приймає непорожній масив arr з n цілочисельних значень у неспадному порядку і число k та перевіряє, чи містить даний масив значення 1, 2, …, k (кожне число від 1 до k щонайменше один раз). Всі інші числові значення заборонені.

Обмеження:

  • n, k - числа на відрізку [1; 300 000]
  • arr містить цілі числа з діапазону [0; 1 000 000 000]
  • arr відсортований у неспадному порядку

Приклади вхідних даних:

  • ([1, 1, 2, 3, 3], 3) -> True
  • ([1, 1, 3], 2) -> False

Код:

1
2
3
4
5
6
7
8
9
def solution(arr, k):
    n = len(arr)
    for i in range(n-1):
        if arr[i]+1 < arr[i+1]:
            return False
    if arr[0] != 1 and arr[n-1] != k:
        return False
    else:
        return True

Рішення:

В циклі ми перевіряємо, щоб кожен елемент + 1 був більший або рівний наступного. Цим забезпечується перевірка на неспадний порядок. Але серед вхідних даних може бути і нуль, тому такий контрприклад валиться: ([1, 0, 0, 1, 2], 2). потрібно додати перевірку на нуль. Підводний камінь: обмеження на вхідні дані.

1
2
if arr[i]+1 < arr[i+1] or arr[i] == 0:
    return False

Друга помилка: логічні оператори. Наступна перевірка здається логічною: перший елемент - це одиниця, останній елемент - це k, а оскільки всі елементи між ними йдуть з кроком нуль або один, то всі необхідні умови виконані.

and перевіряє виконання одразу обох умов, тому якщо перший елемент не одиниця, але останній k або останній не k, проте перший одиниця - повернеться результат True. Контрприклади: ([1, 2, 2, 3, 3], 8), ([3, 4, 4, 5, 5], 5)

1
2
if arr[0] != 1 or arr[n-1] != k:
    return False

Правильний код:

1
2
3
4
5
6
7
8
9
def solution(arr, k):
    n = len(arr)
    for i in range(n-1):
        if arr[i]+1 < arr[i+1] or arr[i] == 0:
            return False
    if arr[0] != 1 or arr[n-1] != k:
        return False
    else:
        return True

Сортування масиву

Є непорожній масив arr, що містить n цілих чисел. Ви можете здійснити одну операцію обміну. Вона приймає два індекси i, j такі, що 0 <= i <= j <= n та міняє місцями значення arr[i] та arr[j]. Написати функцію, яка на основі вхідного масиву буде перевіряти, чи можна здійснити сортування за неспаданням цього масиву, викоставши щонайбліьше одну операцію обміну.

Обмеження:

  • n - число на відрізку [1; 100]
  • arr містить цілі числа з діапазону [1; 1 000 000 000]

Приклади вхідних даних:

  • ([1, 3, 5, 3, 7]) -> True
  • ([1, 3, 5, 3, 4]) -> False

Рішення:

Наївне рішення перебором: беремо пари всіх можливих індексів і робимо для них операцію обміну. Якщо після цього масив стає відсортованим, повертаємо True.

1
2
3
4
5
6
7
8
9
10
def solution(arr):
    n = len(arr)
    arr_sorted = sorted(arr)
    for j in range(0, n):
        for i in range(0, j):
            arr_copy = arr[:]
            arr_copy[i], arr_copy[j] = arr_copy[j], arr_copy[i]
            if arr_copy == arr_sorted:
                return True
    return False

Мінімальна відстань

Є непорожній масив arr, що містить n невід’ємних чисел. Для різних елементів arr[p] та arr[q] (тобто p != q) вводиться поняття відстанні:

  • arr[p] - arr[q], якщо arr[p] - arr[q] >= 0
  • arr[q] - arr[p], якщо arr[p] - arr[q] < 0

Напишіть функцію, яка буде визначати мінімальну відстань між двома різними елементами для даного масиву.

Обмеження:

  • n - число на відрізку [2; 100 000]
  • arr містить цілі числа з діапазону [0; 1 000 000]

Приклади вхідних даних:

  • ([8, 24, 3, 20, 1, 17]) -> 2
  • ([7, 21, 3, 42, 3, 7]) -> 0

Рішення:

Сортуємо масив і послідовно для пар шукаємо їхню відстань. Найменшу записуємо в результуючу змінну.

1
2
3
4
5
6
7
8
def solution(arr):
    min_dist = 1000000
    arr.sort()
    for i in in range(len(arr)-1):
        dist = abs(a[i]-a[i+1])
        if dist < min_dist:
            min_dist = dist
    return min_dist

Підрахунок п’ятірок

Напишіть програму, яка буде отримувати на вхід два цілих числа i, j і повертати скільки елементів на даному проміжку діляться на 5 без остачі.

Обмеження:

  • i, j - числа на відрізку [1; 100 000], i < j

Приклади вхідних даних:

  • (14, 25) -> 3
  • (13, 17) -> 1
  • (35, 55) -> 5
  • (88, 89) -> 0

Рішення:

Перший спосіб - просто використати цикл і лічильник:

1
2
3
4
5
6
def solution(i, j):
    counter = 0
    for k in range(i, j+1):
        if k % 5 == 0:
            counter += 1
    return counter

Другий спосіб - скористатись математичними операціями для прискорення обчислень. Знаходимо ліву та праву поправки (відстань вліво та вправо до найближчих чисел, що кратні п’яти) та ділимо довжину цього проміжку на 5, враховуючи значення поправок.

1
2
3
4
5
6
7
8
9
10
def solution(i, j):
    l_adj = i % 5
    r_adj = 5 - j % 5
    length = j - i + l_adj + r_adj
    result = length / 5
    if l_adj == 0:
        result += 1
    if r_adj != 0:
        result -= 1
    return result

Або включаємо ліву межу, або не забуваємо виключити зайвий елемент правої межі.

Другий спосіб дає значний приріст швидкодії: 0.0029 с проти 56 с (час на 10 000 повторів для проміжку [1; 100 000]).