Последнее оставшееся значение из 2^N целых чисел после удаления Max из четной суммы и Min из пары нечетных сумм

Опубликовано: 19 Сентября, 2022

Учитывая Неотрицательное целое число N , обозначающее первые 2 N положительных целых чисел, где последовательные целые числа, начинающиеся с 1, соединены друг с другом, задача состоит в том, чтобы найти последнее число, оставшееся после выполнения следующих операций:

  • Рассмотрим пару (x, y) двух последовательных целых чисел, которые еще не удалены из 2 N целых чисел.
  • Если сумма двух целых чисел x + y четна, то удалите x (минимальное).
  • Если сумма двух целых чисел x + y нечетная, то удалить y (максимальное).

Примеры:

Input: N = 2
Output: 3
Explanation:
For N = 2 we have 2^N i.e; 4 integers and 4/2 pairs which are as follows-:
(1, 2), (3, 4)
Now after performing the operations:
1 + 2 = 3 which is odd, delete y. So remains 1.
3 + 4 = 7 which is odd,  delete y. So remains 3 
Now the remaining numbers are 1 and 3 and the pair is (1, 3).
Sum = 1  + 3 = 4 which is even, so delete 1.
So the last remaining element is 3.

Input: N = 3
Output: 7
Explanation:
For N = 2 we have 2^N i.e; 8 integers and 8/2 pairs which are as follows-:
(1, 2), (3, 4), (5, 6) and (7, 8)
Now after performing the operations:
1 + 2 = 3 which is odd, delete y. So remains 1.
3 + 4 = 7 which is odd,  delete y. So remains 3.
5 + 6 = 11 which is odd,  delete y. So remains 5.
7 + 8 = 15 which is odd,  delete y. So remains 7.
Now the remaining numbers are 1, 3, 5 and 7 and the pairs are (1, 3), (5, 7).
1 + 3 = 4 which is even,  delete x. So remains 3.
5 + 7 = 12 which is even,  delete x. So remains 7.
Now the remaining numbers are 3 and 7 and the pair is (3, 7)
3 + 7 = 10 which is even, so delete 3.
So the last remaining element is 7.

Подход: Данная проблема может быть решена с использованием следующего математического наблюдения:

  • The idea is to consider when the sum is odd or even while adding two numbers.
    • If we add one even and one odd number then sum will always be an odd number
    • If we add two odd numbers or two even numbers then sum will always be an even number.

На основании вышеприведенного наблюдения решение задачи может быть получено следующим образом:

  • Впервые в каждой паре есть нечетное число и четное число, причем четное число больше. Таким образом, сумма всегда нечетная , а четное число удаляется.
  • На следующих шагах все оставшиеся числа будут нечетными , поэтому сумма пар всегда будет четной. Поэтому альтернативные нечетные числа, начиная с первого (меньшего), удаляются на каждом шаге.
  • Из приведенного выше наблюдения ясно, что максимальным среди всех нечетных чисел будет последнее оставшееся число, т.е. 2 N -1 .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(1)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ