CMI2018-A-10

Question

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);
}

• A. The number of ways of choosing $d$ elements from a set of size $n.$
• B. The number of ways of rearranging $d$ elements from a set of size $n.$
• C. The number of digits in the base $d$ representation of $n.$
• D. The number of ways of partitioning $n$ elements into groups of size $d.$

Comments

foo(7,3) = 2(21)

foo(10,3)= 3(101)

Options c) satisfies

Answer 1

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.

Answer 2

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)

Answer 3

Comments

Could you show a general for of steps as to how you came to this eqn.

 

I understand the answer would be C. But I solved it by trial and error.