PROBLEM LINK:
Setter: Nitish Kumar Tiwari
Tester: Nitin Pundir
Editorialist: Sourav Singh
DIFFICULTY
Easy
PREREQUISITES
Observations, Maths
PROBLEM
Given a number N, output N space-separated integers with the following rules.
-
numi + numj != nump : where I , j and p are from 1 to N and i != j
-
Sum of all the N numbers has to be 2N - 1.
-
number has to be even or 1.
-
Factors of the number must be even or 1.
-
numi < numj where i < j.
OBSERVATION
The sequence 1 + 2 + 4 + . . . 2N-1 yields the sum of 2N - 1
All the above-given conditions are satisfied in the sequence.
EXPLANATION
To get the above sequence we’ll start with the number 1.
- We’ll store 1 in a variable
- Run a loop from 1 to N.
- With each iteration of the loop, first we’ll print the variable and then multiply it by 2.
TIME COMPLEXITY
The time complexity is O(N) . Because of the loop from 1 to N.
SOLUTIONS
Setter's Solution
#include<iostream>
#define ll long long
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 num = 1;
for(int i=0;i<n;i++)
{
cout<<num<<" ";
num *= 2;
}
cout<<endl;
}
}
Tester's Solution
#include<iostream>
#include <vector>
#include <cstdlib>
#include<algorithm>
#include<string>
#include<cmath>
#include<math.h>
#include <list>
#include<bitset>
#define ll long long
using namespace std;
ll md=1000000007;
ll diff=-1;
string mins;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll p=1;
for(ll i=0;i<n;i++,p*=2)
cout<<p<<" ";
cout<<endl;
}
return 0;
}
Feel free to share your approach. Suggestions are welcomed as always.