PROBLEM LINK:
Author: Akash Kumar Bhagat
Tester: Md.Shahid
Editorialist: Akash Kumar Bhagat
DIFFICULTY:
EASY
PREREQUISITES:
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
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())))
