int sum = 0;
for( odd = 1; sum < n ; odd=odd+2)
{
sum = sum + odd;
}
let this loop run k times, then after running k times, what is the value of sum ?
if this loop run 1 time, sum = 1
if this loop run 2 time, sum = 1+3
if this loop run 3 time, sum = 1+3+5
........
if this loop run k time, sum = 1+3+5+........ ( K terms )
so it is a A.P. series,
===> a$_0$ = 1 and difference between two consecutive numbers = 2
Sum = a$_0$ + a$_1$ + a$_2$ + a$_3$ + a$_4$ + ...... +a$_{k-1}$
= a$_0$ + ( a$_0$+ 1 D ) + ( a$_0$+ 2 D ) + ( a$_0$+ 3 D ) + ( a$_0$+ 4 D ) + ...... + ( a$_0$+ (k-1) D )
= K . a$_0$ + ( 1 D ) + ( 2 D ) + ( 3 D ) + ( 4 D ) + ...... + ( (k-1) D )
= K . a$_0$ + ( 1 + 2 + 3 + 4 + ...... + (k-1) ) D
= K . a$_0$ + ( $\frac{(k-1)\;*\;k}{2}$ ) D
substitute D = 2, and a$_0$ = 1 then
= K + ( $\frac{(k-1)\;*\;k}{2}$ ) 2
= K + ( (k-1) * k) = K$^2$
if this loop run K times, then after running k times, value of sum = K$^2$ ----------------- (1)
Now our problem is how much time this loop runs ?
given for loop condition is S < n, that means this loop will stop if S ≥ n
Now let it runs P times and stops
===> (1+3+5+....+P) ≥ n
===> P$^2$ ≥ n
P$^2$ ≥ n ===> P ≥ $\sqrt{n}$
if n is a perfect square, then P = $\sqrt{n}$ ===> as per eqn (1), sum will exactly equal to n.
if n is not a perfect square, then P = ⌈$\sqrt{n}$⌉ ===> as per eqn (1), sum should be grater than n