 # ECAPR203-Editorial

Author: Akash Kumar Bhagat
Tester: Md.Shahid
Editorialist: Akash Kumar Bhagat

EASY

Maths

# PROBLEM:

The problem states a sequence which goes like- 0,1,0,1,2,0,1,2,3,0 . In other words, the sequence starts from 0 and get incremented till i(initially i=1), after that it restarts from 0 while i is increased to (i+1).The problem asks us to find the Nth element in ths sequences.

# EXPLANATION:

The sequence:- 0 , 1 , 0 , 1 , 2 , 0 , 1 , 2 , 3 , 0 , 1 , 2 , 3 , 4 , 0
Index       :- 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10, 11, 12, 13, 14, 15


If we carefully observe the Sequence and notice the position of 0(as the sequence restarts from it), 0 occupies the following index:-1,3,6,10,15...... From here one can conclude that \forall x in 1,2,3,4…\infty there is a 0 at x(x+1)/2. Hence to find the Nth element, one has to find the latest postion of 0.

Since we know that 0 occupies the position of x(x+1)/2 we can easily iterate for each x until we find x(x+1)/2 \leq N. But the constrain don’t allow us to iterate, Hence we have to find x through the quadratic equation

x(x+1)/2 \leq N \Rightarrow x^2 +x \leq 2N

x^2 + x - 2N \leq 0

x=\frac{-1 \pm \sqrt{1+4*2N}}{2}

Since x will be positive,x=\frac{-1 + \sqrt{1+4*2N}}{2}

There is a much easier way to find x.

x=sqrt(2*N)
if x(x+1)/2 > N
x-=1


If we found x such that x(x+1)/2 \leq N, i.e we found the latest occurence of 0.Here the answer will be N-x(x+1)/2

Please share your approach to the problem   # SOLUTIONS:

CPP
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long int
#define vi vector<int>
#define vvi vector<vector<int>>
#define pll pair<ll, ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vpll vector<pair<ll,ll>>
#define umap unordered_map
#define uset unordered_set
#define all(c) c.begin(), c.end()
#define maxarr(A) *max_element(A, A+n)
#define maxvec(v) *max_element(all(v))
#define present(map,elem) map.find(elem)!=map.end()
#define lb(v,elem) lower_bound(all(v),elem)
#define ub(v,elem) upper_bound(all(v),elem)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define For(i,a,b) for(int i=a; i<b; ++i)
#define rep(i,a,b) for(ll i=a; i<b; ++i)
#define debug(v) for(ll i=0; i<v.size(); i++) cout<<v[i]<<" "; cout<<endl;
#define debugn(v,n) for(ll i=0; i<n; i++) cout<<v[i]<<" "; cout<<endl;
#define mod 1000000007
#define endl '\n'

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("1.in","r",stdin);
int t;
cin>>t;
while(t--){
ll n;
cin>>n;
ll tn=0,tm=0;
ll l=1, h=(ll)1e10;
while(h>l){
ll m = (l+h)/2;
ll x = (m*(m+3))/2;
if(x<=n){
tn= m;
tm = x;
l = m+1;
}else{
h = m;
}
}
if(tm==n){
cout<<tn<<endl;
}else{
cout<<n-tm-1<<endl;
}
}

return 0;
}

Python
import math
F=lambda c:c*(c+1)//2
def Solve(n):
x=int(math.sqrt(2*n))
if n>=F(x):
return n-F(x)
else:
return n-F(x-1)

for i in range(int(input())):
print(Solve(int(input())))



Hi. Can you please expand more on the reason behind the easier way to find x:

x=sqrt(2*N)
if x(x+1)/2 > N
x-=1


I am not able to understand this

1 Like

hey @makkoncept,
The generalised way to find x is through Quadratic equation,
x=\frac{-1+\sqrt{1+4*2N}}{2}

i.e x=\frac{-1}{2}+\frac{\sqrt{1+4*2N}}{2}

i.e x=\frac{-1}{2}+\frac{\sqrt{4*2N}}{2} (if we ignore 1)

i.e. x=\frac{-1}{2}+\sqrt{2N}

So basically we can induce x=\sqrt{2N}

But it won’t work for every case, for example when N=9, x must be 3 but the \sqrt{2N} will give us 4 which is incorrect. Hence it is required to check x such that x(x+1)//2 \leq N.

1 Like

Got it. Thanks 1 Like

Why maths problem, Please have DSA problem

P.S: I am bad at maths btw: great explaination and problem too!

1 Like