Последнее оставшееся значение из 2^N целых чисел после удаления Max из четной суммы и Min из пары нечетных сумм
Учитывая Неотрицательное целое число 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)