PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Sandeep V
Tester: Radostin Chonev
Editorialist: Nishank Suresh
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given N, find N+1 positive integers whose sum is 2^N and exactly one of them appears twice, while the others appear once.
QUICK EXPLANATION:
One possible solution is 1, 1, 2, 4, \dots, 2^{N-1}.
EXPLANATION:
Trying to find the answers on paper for small N should lead to the following observations:
- The only solution for N = 1 is [1, 1].
- The only solution for N = 2 is [1, 1, 2].
- One possible solution for N = 3 is [1, 1, 2, 4]
\vdots
From here, it is easy to observe that the array [1, 1, 2, 4, \dots, 2^{N-1}] always works as a solution.
Proof
2^i < 2^{i+1} for i\geq 0, so the only repeated number in our set is 1.
Further,
as required.
TIME COMPLEXITY:
\mathcal{O}(N)
CODE:
Setter (Python)
t=int(input())
for _ in range(t):
n=int(input())
print(1,end=" ")
for i in range(n):
print(2**i,end=" ")
print()
Tester (C++)
#include<bits/stdc++.h>
using namespace std ;
int n ;
void input ( ) {
cin >> n ;
}
void solve ( ) {
cout << "1 " ;
for ( int i = 0 ; i < n ; ++ i ) {
cout << ( 1LL << i ) << " \n"[ i == n - 1 ] ;
}
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t ;
t = 1 ;
/// scanf ( "%d" , &t ) ;
cin >> t ;
while ( t -- ) {
input ( ) ;
solve ( ) ;
}
return 0 ;
}
Editorialist (Python)
import sys
input = sys.stdin.readline
for _ in range(int(input())):
n = int(input())
print('1 ' + ' '.join(str(2**i) for i in range(n)))