Read problem statements in [Mandarin], [Russian], and [Vietnamese] as well.

You are given a positive integer N. You have to print exactly N + 1 positive integers 
satisfying the following conditions:

Exactly one value should appear twice, all the remaining values should appear only once.
Sum of all these values should be equal to 2^{N}.

You have to print the values in non-decreasing order. If there are multiple solutions, you can print any of them.

------ Input Format ------ 

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains a single integer N.

------ Output Format ------ 

For each test case, print a single line containing N + 1 positive integers in non-decreasing order that satisfy the given conditions. If there are multiple solutions, you may print any of them.

------ Constraints ------ 

$1 ≤T ≤60$
$1 ≤N ≤60$

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------ 
2
3
4

----- Sample Output 1 ------ 
1 2 2 3
1 2 3 3 7
----- explanation 1 ------ 
Test Case $1$: $2$ is repeated twice and the remaining elements occurred only once and the sum of all the elements is equal to $8$, which is $2^{3}$.

Test Case $2$: $3$ is repeated twice and the remaining elements occurred only once and the sum of all the elements is equal to $16$, which is $2^{4}$.

Difficulty: MEDIUM
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for t in range(int(input())):
	n = int(input())
	if n == 1:
		print(1, 1)
		continue
	ans = []
	for i in range(n - 1):
		ans.append(i + 1)
	ans.append(n - 1)
	ans.append(2 ** n - n * (n + 1) // 2 + 1)
	print(*ans)


T = int(input())
for i in range(T):
	N = int(input())
	if N == 1:
		print(1, 1)
		continue
	ans = []
	for i in range(0, N - 1):
		ans.append(i + 1)
	ans.append(N - 1)
	ans.append(2 ** N - N * (N + 1) // 2 + 1)
	for i in ans:
		print(i, end=' ')
	print()


T = int(input())
for i in range(T):
	n = int(input())
	if n == 1:
		print(1, 1)
		continue
	Val = []
	for i in range(n - 1):
		Val.append(i + 1)
	Val.append(n - 1)
	Val.append(2 ** n - n * (n + 1) // 2 + 1)
	for j in Val:
		print(j, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1, 1)
	elif n == 2:
		print(1, 1, 2)
	else:
		sum = 0
		for i in range(1, n - 1):
			sum += i
			print(f'{i} ', end='')
		print(f'{n - 1} ' * 2, end='')
		sum += 2 * (n - 1)
		print(2 ** n - sum)


t = int(input())
for i in range(t):
	n = int(input())
	print('1 1' if n == 1 else ' '.join((str(x) for x in list(range(1, n)) + [n - 1, 2 ** n - int((n - 1) * (n + 2) / 2)])))


for _ in range(int(input())):
	n = int(input())
	sumi = 2 ** n
	if n > 1:
		new = [i for i in range(1, n)]
		new.append(n - 1)
		new.append(sumi - sum(new))
		print(*new)
	else:
		print(1, 1)


for _ in range(int(input())):
	n = int(input())
	s = 0
	if n == 1:
		print('1 1')
	else:
		for i in range(1, n + 1):
			if i > n - 2:
				print(n - 1, end=' ')
				s += n - 1
			else:
				print(i, end=' ')
				s += i
		print(2 ** n - s)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1, 1)
	else:
		k = list((x for x in range(1, n)))
		k.append(n - 1)
		k.append(2 ** n - sum(k))
		print(*k)


T = int(input())
for w in range(T):
	N = int(input())
	sum_N = N * (N + 1) // 2
	num = 2 ** N - sum_N
	if num <= N:
		for i in range(1, N + 1):
			print(i, end=' ')
			if i == num:
				print(i, end=' ')
	else:
		for i in range(1, N):
			print(i, end=' ')
		print(N - 1, end=' ')
		print(num + 1, end='')
	print()


for _ in range(int(input())):
	n = int(input())
	target = 2 ** n
	if n == 1:
		print(1, 1)
		print()
	else:
		for i in range(1, n):
			print(i, end=' ')
		print(n - 1, end=' ')
		target -= (n - 1) * n // 2 + n - 1
		print(target, end=' ')
		print()


for i in range(int(input())):
	n = int(input())
	su = 2 ** n
	l1 = [i for i in range(1, n + 1)]
	s = sum(l1)
	diff = su - s
	if diff <= max(l1):
		l1.append(diff)
	else:
		l1[-1] = l1[-1] - 1
		p1 = sum(l1)
		xq = su - p1
		l1.append(xq)
	l1.sort()
	for j in l1:
		print(j, end=' ')
	print()


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	s = 2 ** n
	if n == 1:
		print(1, 1)
	else:
		l = [i for i in range(1, n)]
		l = l + [l[-1]]
		l.append(s - sum(l))
		print(*l)


for _ in range(int(input())):
	n = int(input())
	arr = [i for i in range(1, n + 1)]
	x = 2 ** n - n * (n + 1) // 2
	if x > n:
		x = x + 1
		arr[n - 1] -= 1
	arr.append(x)
	arr.sort()
	print(*arr)


t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print('1 1')
	elif n == 2:
		print('1 1 2')
	elif n == 3:
		print('1 2 2 3')
	else:
		sum = 2 ** n
		i = 1
		t = n + 1
		while t > 3:
			print(i, end=' ')
			sum -= i
			i += 1
			t -= 1
		print(i, i, end=' ')
		sum -= 2 * i
		print(sum)