recategorized by
972 views
4 votes
4 votes
The function defined for positive integers by

$F\left ( 1 \right )=1 F\left ( 2 \right )=1 F\left ( 3 \right )=-1$

and by identites

$F\left ( 2k \right )=F\left ( k \right ), F\left ( 2k+1 \right )=F\left ( k \right ) for\; k>=2$

then

sum $F\left ( 1 \right )+F\left ( 2 \right )+F\left ( 3 \right )+....................+F\left ( 100 \right )$ is___ ??
recategorized by

2 Answers

Best answer
13 votes
13 votes

Let me take any arbitrary number and try to find what value it gets mapped under function F.

For n=100 (say) what is $F(100)$ ?

$F(100)=F(50)=F(25)=F(12)=F(6)=F(3)=-1$. Finally $F(100)$ becomes $-1$. But it's not a good idea to start with higher values as it leads to many calls to F. If we start with lower values then you will see that our computation overhead will be very less.

(It is like using Dynamic Programming in Bottom Up fashion. If you don't know dynamic programming then No problem, It is not required at all, Continue further.)

Observe that what $F(2)$ generates? (since recursive equation is defined for $k\geq2$ so I can not put k=1 there. I am starting with k=2 and k=3)

$F(2)=F(4)$ and $F(2)= F(5)$.

Similarly see, what $F(3)$ generates?. $F(3) =F(6)$ and $F(3)=F(7)$.

In this way, we can make a tree and this problem is done. :)

  • $\begin{align*} &\sum_{k=1}^{100}F(k) = 32 - 5 + 1 = \bf \large \color{red}28 \\ \end{align*}$
edited by
5 votes
5 votes

Create a complete binary tree using these 100 integers. 1st element is root. 2nd and 3rd are left and right children of root. You can store this tree in an array just like you store a heap. Now its given that $F(2k+1) = F(k)$ and $F(2k) = F(k)$. So each element in the subtree of 2nd element will be 1 and each element in subtree of 3rd element will be -1. Fill this tree till 6th level (root at level 1), then total nodes $= 1 + 2 + 4 + 8 + 16 + 32 = 63$. Remaining nodes $= 100 - 63 = 37$. Note that the sum of all nodes till now is just 1 (root) because $Size \;of\; left\; subtree\; of\; root\; = \;Size\; of\; right\; subtree\; of\; root$.

Now we need to fill the $7th$ level. Number of nodes possible on this level $= 2^6 = 64$. Out of these $64$, 32 will be $1$ and 32 will be $-1$. But we have only 37 remaining nodes. So 32 of them will be 1 and the remaining will be -1. So the answer is $32-5+1 = 28$ (+1 for root)

edited by

Related questions

1 votes
1 votes
1 answer
2
Ayush Upadhyaya asked Jul 20, 2018
371 views
Consider the following function$f(x)=\frac{x}{2x+1} , \, x\not= -\frac{1}{2}$Is the function a bijection?Yes, this is a one-to-one function.For onto, let's suppose functi...
0 votes
0 votes
0 answers
3
1 votes
1 votes
1 answer
4
Lakshman Bhaiya asked Feb 20, 2018
754 views
The figure which represents $y = \dfrac{sin x}{x}$ for $x>0$ ($x$ in radians) is