# N1VALUES - Editorial

Author: Sandeep V
Editorialist: Nishank Suresh

Cakewalk

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,

1 + 1 + 2 + 4 + \dots + 2^{N-1} \\ = 1 + (1 + 2 + 4 + \dots + 2^{N-1}) \\ = 1 + (2^N - 1) = 2^N

as required.

\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
for _ in range(int(input())):
n = int(input())
print('1 ' + ' '.join(str(2**i) for i in range(n)))

1 Like

What is the wrong in this code?PLZ help

#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define MOD 1000000007
#define pb push_back
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin >> t;
while (t–)
{
ll n;
cin>>n;
ll dup = pow(2,n) - ((n*(n+1))/2);

    vector<ll> v(n+1);
for(ll i=0;i<n;i++)
v[i]=i+1;

ll res = dup-n;
if(res%2==0)
{
dup-=(res/2);
v[n]=dup;
v[n-1]=n+(res/2);

}
else
{
res++;
v[n-2]=n-1+(res/2);
dup-=(res/2);
v[n]=dup;
if(v[n-2]>v[n-1])
swap(v[n-1],v[n-2]);
}

if(n<=3)
swap(v[n-1],v[n]);
for(ll i=0;i<n+1;i++)
cout<<v[i]<<" ";
cout<<"\n";

}

return 0;


}

What is wrong with this solution? Pls tell.

#include
using namespace std;

int main() {
int t;
cin >> t;
while(t–){
long long n, sum;
cin >> n;
if(n == 1)
cout << “1 1” << endl;
else {
sum = 1 << n;
for(int i = 1; i <= n-2; i++)
cout << i << " ";
cout << n-1 << " " << n-1 << " ";
long long res = (sum - ((((n-2) * (n-1))>>1) + ((n-1)<<1)));
cout <<res << endl;
}
}
return 0;
}

What’s the problem with this solution:

#include<bits/stdc++.h>
using namespace std;

#define ll long long

void solve(){
int n;
cin >> n;
ll sum = 0;
ll a = pow(2, n);

for(ll i = 0; i < n-1; i++){
sum += i;
}

sum += 2*(n-1);

ll b = a - sum;

for(int i=1; i < n-1; i++){
cout << i << " ";
}

cout << n-1 << " " << n-1 << " " << b;

cout << "\n";


}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

 int t;
cin >> t;

while(t--){
solve();
}

return 0;


}

Please refer the video editorial for better understanding.

1 Like

why this this isn’t working?, Using the same approach.

You have to print in increasing order.
This code printing 1 at the end.

t = int(input())
for i in range(t):
n = int(input())
sum=0
l=[]
for i in range(1,n):
l.append(i)
sum+=i
l.append(n-1)
sum+=(n-1)
l.append((2**n)-sum)
print(*l)



what is wrong in this code? pls tell

cout << ( 1LL << i ) << " \n"[ i == n - 1 ] ;

In the testers code. How does this link work. Is there some kind of conditnal printing here
@ronniechonev

For n = 1, your output is

0 2


which is wrong because the statement asks for positive integers.

1 Like

Treat " \n" as a string of length 2, then you can see that " \n"[ i == n - 1 ] prints a space when i is not n-1 and prints a newline when it is.

3 Likes

That’s a crazy way of handling the output format.

1 Like

This code satisfie all conditions still it’s wrong, why? Please help me to rectify my mistake in it.

#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t–)
{
int n;
cin >> n;
long long int a[61];
a[0] = 1;
a[1] = 1;
int sum = 2;
for (int i = 2; i <= n - 1; i++)
{
a[i] = i;
sum = sum + a[i];
}
if (n != 1)
{
a[n] = pow(2, n) - sum;
}
for (int i = 0; i <= n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
return 0;
}

here u can check for a case n=1 print “1 1”(its not taking 0 as positive integer here)

The solution can be find below as well as here.

#include <bits/stdc++.h>
using namespace std;

int main() {
int t; cin >> t;
while (t--) {
int n; cin >> n;
int sum = pow(2, n) - 2;
cout << "1 1";
int counter = 2;
for (int i = 1; i < n - 1; i++) {
cout << " " << counter;
sum -= counter;
counter++;
}
if (n != 1) cout << " " << sum;
if (t != 0) cout << endl;
}
return 0;
}


For input:

6
1
2
3
4
5
6


Output is correct:

1 1
1 1 2
1 1 2 4
1 1 2 3 9
1 1 2 3 4 21
1 1 2 3 4 5 48


Always test the boundary values!

[simon@simon-laptop][09:41:57]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh
Compiling heatherstanton-N1VALUES.cpp
Executing command:
g++ -std=c++17 heatherstanton-N1VALUES.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG    -fsanitize=undefined -ftrapv
heatherstanton-N1VALUES.cpp: In function ‘int main()’:
heatherstanton-N1VALUES.cpp:8:26: warning: conversion to ‘int’ from ‘__gnu_cxx::__promote_2<int, int, double, double>::__type {aka double}’ may alter its value [-Wfloat-conversion]
int sum = pow(2, n) - 2;
~~~~~~~~~~^~~
^R
Successful
[simon@simon-laptop][09:42:03]
[~/devel/hackerrank/otherpeoples]>echo "1
60" | ./a.out
heatherstanton-N1VALUES.cpp:13:17: runtime error: signed integer overflow: -2147483648 - 2 cannot be represented in type 'int'
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 2147481879

1 Like

I got my mistake!! i needed to use long long int…now it’s work

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
int n;
cin>>n;
ll k=1;
vector<ll>v;
for(int i=1;i<=n+1;i++){
if(i==1||i==2)
v.push_back(1);
else
v.push_back(pow(2,k++));
}
for(int i:v)
cout<<i<<" ";
cout<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}


here you go

#include <bits/stdc++.h>

using namespace std;

int main() {

int t; cin >> t;

while (t--) {

long long int n; cin >> n;

long long int pw=pow(2,n);

long long int sum =  pw- 2;

cout << "1 1";

long long int counter = 2;

for (int i = 1; i < n - 1; i++) {

cout << " " << counter;

sum -= counter;

counter++;

}

if (n != 1) cout << " " << sum;

if (t != 0) cout << endl;

}

return 0;


}

1 Like