N1VALUES - Editorial

editorial
, ,
1

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,

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

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)))
2 Likes
2

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;

}

3

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;
}
}
// your code goes here
return 0;
}

4

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;

}

5

Please refer the video editorial for better understanding.

1 Like
6

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

7

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

8 
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)
9

what is wrong in this code? pls tell

10

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

11

For n = 1, your output is

0 2

which is wrong because the statement asks for positive integers.

2 Likes
12

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
13

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

1 Like
14

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;
}

15

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

16

Please help, I’m still not able to understand. Why the above solution is not getting accepted.

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

But still shows wrong answer. @ssjgz @sharad_0_1

17

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
18

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

19 
#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;
}

why I am getting WA? please help.

20

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