Problem:-
Paraphrase:-
We have a sequence 0,1,0,1,2,0,1,2,3,0,1,2,3,4....\infty, given n and we’ll have to find n^{th} digit in the sequence.
My Approach:-
\Large\frac{(x)*(x+1)}{2} \ge n then I print, n -\Large\frac{(x)*(x-1)}{2} - 1
for(i=2, sum=0; ; i++)
{
if( sum + i > n )
{
cout << n - sum - 1 << '\n';
break;
}
sum = (i * (i+1)) / 2;
}
and since n goes as much as 10^{18} , test cases are 10^3 and obviously I get TLE at > 1 sec since my approach is O(\sqrt n) -ish. The answer should be in < O(\sqrt n) probably O(1), I figured that much and couldn’t understand the math logic behind AC solutions.
Can someone tell me a better approach.
@akay_99
Thanks for your time, you helped me grow 
.
2 Likes
Sorry, for editing it quite many a times…
Dude, thank you for using latex, it’s so refreshing to see!
There are two ways to optimize your solution.
The first is to just binary search on x, for O(\log{n}).
For the O(1), you can directly solve for the value of x.
You have the equation: \dfrac{x(x+1)}{2} \geq n, which is a quadratic equation and can be solved for by manipulating the equation:
x(x + 1) \geq 2n
x^2 + x \geq 2n
x^2 + x - 2n \geq 0
n is like a constant, so we can apply the quadratic formula:
x \geq \dfrac{-1 \pm \sqrt{1 + 4\cdot2n}}{2}
Since we’re operating with integers, we always want to round up, so we get an explicit formula:
x = \left \lceil \dfrac{-1 \pm \sqrt{1 + 8n}}{2} \right \rceil
which is probably similar to the math you saw in some accepted solutions. Note that for the \pm, we’re only interested in the + since using the - will lead to a negative x.
3 Likes
@galencolin,
Well, the least I could is not give an eyesore to people who try help me right 
.
And yeah I thought of solving for roots using that, but then since there would be a round off I thought it’s not going to give me a correct solutions for all values of n. And how did you change the inequality to equal, just by using round off , is it a valid way ?.. I’m poor in math 
We want the smallest x that satisfies x \geq \dfrac{-1 \pm \sqrt{1 + 8n}}{2}.
Either this value of x is an integer, which means we don’t have to do anything, or it’s not. If it isn’t, then if we round down, \lfloor x \rfloor will be too low and won’t satisfy the condition. So either x is an integer (so rounding up wouldn’t change anything), or we have to round up.
2 Likes
Tried with a sample n, and worked, thumbs up
Oh, I see n = 6, it’s
\large x = \Large \frac {-1 \pm \sqrt {1 + 8*6}} {2}
\large x = \Large \frac {-1 \pm \sqrt {1 + 48}} {2}
\large x = \Large \frac {-1 \pm \sqrt {49}} {2}
\large x = \Large \frac {-1 \pm 7} {2}
\large x = \Large \frac {6} {2}
\large x = 3
Now,
\Large \frac {(3) * (3-1)}{2} = 6
n - 6 = 6 - 6 = 0 which is what we wanted.
Wow, it worked, math is cool.
@galencolin,
Look at this AC solution. Why did he/she partially ignore the quadratic root formula?
https://www.codechef.com/viewsolution/32314416
x=sqrt(2*n);
ans =(x*(x-1))/2;
n-=ans;
cout<<n%x<<endl;
\large x = \Large \frac {-1 \pm \sqrt {1 + 4*2*n}} {2}
Apparently, I guess he ignore both -1 and 1(inside root) and made it,
\large x = \Large \frac {\sqrt { 4*2*n}} {2}
\large x = \Large \frac {2\sqrt { 2*n}} {2}
x = \sqrt { 2*n}
Even though he ignore those 1's how did he achieve the desired answer?
You helped me a lot today 
, thanks again and sorry for taking too much of your time .
2 Likes
Well, I ran a stress-test with 10^9 random cases and it passed all of them, so the solution is probably indeed correct beyond passing CodeChef’s (limited) testset.
By default, they use \lfloor \sqrt{2n} \rfloor, so it’s not exactly equivalent to ignoring the -1 and 1. But honestly, I have no idea why it works the same way.
3 Likes
Oh, thanks @galencolin …you’re of great help to me today. The sad thing is that, I’ve come across codes that used to similar \sqrt{2n} implementation instead of using entire quadratic root(s) formula but never been able to understand why mathematically. Actually, only after seeing that code, did I post this discussion.
I can let it go of the 1 inside root. Since in our approach we are rounding the value to either left neighborhood or to the right neighborhood but not both (sometimes left and something right, and if we want to do both operations then we need to develop a f(x) which determines when to floor and ceil right?). As, we are sticking to either left or right neighborhood it shouldn’t be a problem. Also, that inside 1 is so insignificant as we approach \infty , so we can let the inside 1 slide but the -1 outside is still a mystery.
It’s weird because it’s like you subtract something but still nothing changes…
1 Like
@eddie_code5
In this question, our main motive is to find x such that x*(x+1)/2 is just less than n. For this as @galencolin said, one can use the quadratic equation to find x ,but there is a much simpler way too,
x=sqrt(2*n)
if x*(x+1)//2>n :
x-=1
For example if n=9 ,x must be 3 because 3*(3+1)//2=6 <9, but if use sqrt(2n) here this will yield us 4 which is not correct .(4*(4+1)//2=10>9).
so if we found x, the answer will be
n-x*(x+1)//2
We will soon upload editorial and video explanation of each problem soon
2 Likes
@akay_99,
That’s a thought full approach isn’t.
But the part where I’m suck is that, how did one thought of using x = \sqrt{2*n} -1 and not x = \sqrt{n} or anything else…I don’t think it’s just intuition to use x = \sqrt{2*n} -1 … so there must be a mathematical reason on why people used it and I’m kinda in search of it.
Thanks for your time and help
1 Like
Hey @eddie_code5,
The given sequence was
0,1,0,1,2,0,1,2,3,0 if we index this from 1,
1,2,3,4,5,6,7,8,9,10 here notice the position. Here the thing to notice is the position of 0 as the sequence restarts from it. So 0 occupies the index of 1,3,6,10,15....
i.e for all x in 1,2,3,4..... there is a 0 at x*(x+1)/2 th index.
Hence we find the x such that n>= x(x+1)/2. Here x(x+1)/2 will give us the position of the latest 0
1 Like