Наибольший набор чисел до N, в котором присутствует либо i, либо i/2.
Учитывая положительное целое число N , задача состоит в том, чтобы найти длину наибольшего набора, который может быть сгенерирован таким образом, что если i присутствует, то i/2 не будет присутствовать и 1<=i<=N .
Note: For multiple solutions, print anyone satisfying the condition.
Примеры:
Input: N = 2
Output: 1
Explanation: There are two possible values 1 and 2. If 2 is present, 1 can not be present since 2/2=1. So only possibilities are 1 or 2. Both 1 and 2 separately can be the answers.Input: N = 10
Output: 1 3 4 5 7 9
Explanation: In the output, there are no i for which i/2 exists.
Подход: Создайте карту для удобного хранения и поиска и вектор для хранения окончательного набора. Запустите цикл от 1 до N (скажем, i ). Если i нечетное, добавьте i к вектору ответа и в качестве ключа на карте. В противном случае, если я четный, найдите i/2 как ключ на карте. Если i/2 отсутствует на карте, то добавьте i к вектору ответов и в качестве ключа на карте. Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте карту <int, bool> mp[].
- Инициализируйте vector<int> ans[] для сохранения результата.
- Перебрать диапазон [, N] с помощью переменной i и выполнить следующие задачи:
- Если i нечетное, то вставьте i в вектор ans[] и вставьте {i, 1} в карту mp[].
- В противном случае, если i/2 не существует в карте mp[] , тогда поместите i в вектор ans[] и вставьте {i, 1} в карту mp[].
- После выполнения вышеуказанных шагов выведите значения вектора ans[] в качестве ответа.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N)
Вспомогательное пространство: O(N)