Question

What is the return value of following function for 484? What does it to in general?

bool fun(int n) {     int sum = 0;     for (int odd = 1; n > sum; odd = odd+2)        sum = sum + odd;     return (n == sum); }

(A) False, it checks whether a given number is power of 3
(B) False, it checks whether a given number is even or not
(C) False, it checks whether a given number is odd or not
(D) True, it checks whether a given number is perfect square.

 

Any one can explain output of above program?

Comments

Answer is D! @Shaik Masthan He wants to know the mathematical logic behind the function

---

@Shivam Kasat

i know brother....

but what i am saying is, if you want to find a general case, then you should do a derivation to conclude that statement... That's why i am asking where he struck while deriving the statement.

anyway i added the derivation.... 

i know this much time not there in the exam, but learning a general approach is better while practicing.

---

What does return(n==sum) mean? Is it a condition checking?

Answer 1

Try for smaller value like fun(25).

every time sum will be incremented like 0,1,4,9,16,25 similarly "ODD" variable define inside for loop will be updated like 1,3,5,7,9,11. At the end of for loop return will check weather n==sum, return true which means given number is the perfect square.

Answer 2

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