The Gateway to Computer Science Excellence
+2 votes
24 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.$
in Programming by Boss (16.8k points)
recategorized by | 24 views
0
foo(7,3) = 2(21)

foo(10,3)= 3(101)

Options c) satisfies

1 Answer

0 votes

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 (21.7k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,523 answers
195,602 comments
101,282 users