Задачник по алгоритмам

Программа курса:

Задача 5: K-я наименьшая простая дробь

Напишите определение функции kthSmallestPrimeFraction(arr, k):, которая принимает два аргумента:

  1. arr — отсортированный массив целых чисел, содержащий 1 и простые числа. Все числа в массиве уникальны.
  2. k — целое число, представляющее порядковый номер дроби.

Функция должна вернуть массив из двух целых чисел [a, b], где a и b — числитель и знаменатель k-й наименьшей дроби, которая рассматривается.

Подробное описание:

Для каждого индекса i и j, где 0 <= i < j < arr.length, мы рассматриваем дробь arr[i] / arr[j].

Нужно вернуть k-ю наименьшую дробь (в порядке возрастания).

Примеры:

Пример 1:

Ввод:
arr = [1,2,3,5], k = 3
Вывод:
[2,5]

Пояснение:
Все дроби в порядке возрастания:
1/5, 1/3, 2/5, 1/2, 3/5, 2/3.
Третья дробь — 2/5.

Пример 2:

Ввод:
arr = [1,7], k = 1
Вывод:
[1,7]

Пояснение:
Единственная дробь — 1/7.

0
Вы должны Войти или Зарегистрироваться чтобы оставлять комментарии