# CMI2018-A-10

116 views

What does the following function compute in terms of $n$ and $d$, for integer value of $n$ and $d,d>1?$ Note that $a//b$ denotes the quotient(integer part) of $a \div b,$ for  integers $a$ and $b$. For instance $7//3$ is $2.$

function foo(n,d){
x := 0;
while (n >= 1) {
x := x+1;
n := n//d;
}
return(x);
}
1. The number of ways of choosing $d$ elements from a set of size $n.$
2. The number of ways of rearranging $d$ elements from a set of size $n.$
3. The number of digits in the base $d$ representation of $n.$
4. The number of ways of partitioning $n$ elements into groups of size $d.$

recategorized
0
foo(7,3) = 2(21)

foo(10,3)= 3(101)

Options c) satisfies

Suppose we take $n = 7$ and $d = 2$

n=7  //First iteration of while loop
{
x=1,
n = 7//2 = 2
}

n=2 //Second iteration of while loop
{
x=2 ,
n = 2//2 = 1
}

n=1 // Third iteration of while loop
{
x=3 , n=1//2 = 0.
}
// while loop terminates.

Returns value of $x$  which is $3$

Suppose we have set S ={ 1,2,3,4,5,6,7} , n=7 , d=2.

We can choose $2$ elements in $\frac{7*6}{2*1}= 21$ So option $A$ is incorrect.

We can rearrange any two elements from the set S by only $1$ way i.e by swapping them so Option $B$ is also incorrect.

We can partition these $7$ elements into group of $2$ elements in more than $4$ ways so option $D$ is also incorrect.

Hence option $C$ is the correct choice.

As we can see from the program execution it is just counting the number of divisions that we perform when we convert an decimal to a base $d$ number system and storing that value in $x$.

like suppose we need to convert $7$ into base $2$ number system. so we do $3$ divisions as follows.

2|   7    |  1

2|   3     | 1

2|   1     | 1

0

Hence option $C$ is the correct choice.

Take k=2 and n = 7

n = 7 --------------------> 7//2=3 -----1

n=3----------------------->3//2=1 ------1

n=1----------------------->1//2=0--------1

n=0 will not execute

Total is 1+1+1 = 3 which is the number of digits in base 2 representation of 7 so, C)

## Related questions

1
265 views
Which of the words below matches the regular expression $a(a+b)^{\ast}b+b(a+b)^{\ast}a$? $aba$ $bab$ $abba$ $aabb$
1 vote
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$ $2$ $-1$ $0$ $1$