41 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 | 41 views
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.

by Boss (23.7k points)

+1 vote