Мощные целые числа (Leetcode 970) -
Сложность: Средняя ссылка: День 30: апрельское испытание Leetcoding. Даны три целых числа x, y и граница, вернуть список всех… theswiftnerd.com



Вы также можете прочитать полную историю в блоге The Swift Nerd вместе с другими интересными статьями по ссылке выше.

описание проблемы

Учитывая три целых числа x, y и bound, верните список всех мощных целых чисел, значение которых меньше или равно bound.

Целое число считается мощным, если его можно представить как xi + yj для некоторых целых чисел i ›= 0 и j› = 0. Вы можете возвращать ответ в любом порядке. В вашем ответе каждое значение должно встречаться не более одного раза.

Пример 1:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

Пример 2:

Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]

Ограничения

  • 1 <= x, y <= 100
  • 0 <= bound <= 106

Решение

Проблема состоит в том, чтобы просто найти целые числа (i, j), которые удовлетворяют условию xi + yj ‹= bound. Мы можем использовать грубую силу для итерации с двумя вложенными циклами и проверки, меньше ли сумма обоих членов границ. Мы можем использовать структуру set, чтобы избежать дублирования ответов. Затем мы можем заставить наши вложенные циклы увеличивать мощность значений x и y, добавляя соответствующие результаты к нашему набору. Максимальное значение любых терминов, составленных с x или y, ограничено - 1 (почему, потому что x, y ›= 1, поэтому, если какой-либо из них становится 1, то максимальное значение другого термина = bound - 1 ).

Edge Case

Нам нужно позаботиться о случае, когда x или y = 1. Скажем, y = 1, тогда для каждой степени i yi = 1, и это станет бесконечным циклом. Итак, в конце последовательных циклов мы можем проверить x = 1 и y = 1 и выйти, потому что все возможные значения других членов были бы достигнуты в текущей итерации.

Анализ сложности

Операции, необходимые x для достижения границ, - это LogX (Bound). Точно так же максимальное количество операций для y для достижения границ - это LogY (Bound). Следовательно, общее количество операций будет иметь порядок O (LogX (Bound) * LogY (Bound)), что огромно, потому что с увеличением мощности будут ограниченные целые числа, удовлетворяющие условиям. То же самое и с космосом.

Время = O (LogX (привязано) * LogY (связано))

Пробел = O (LogX (связанный) * LogY (связанный))

Спасибо за чтение. Если вам понравилась эта статья и вы нашли ее полезной, поделитесь ею и распространите ее как лесной пожар!

Вы можете найти меня на TheSwiftNerd | LinkedIn | Github