search
Log In
4 votes
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.$
in Programming
recategorized by
116 views
0
foo(7,3) = 2(21)

foo(10,3)= 3(101)

Options c) satisfies

2 Answers

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.

0 votes

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

2 votes
3 answers
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$
asked Sep 13, 2019 in Theory of Computation gatecse 265 views
1 vote
2 answers
2
118 views
Akash, Bharani, Chetan and Deepa are invited to a party. If Bharani and Chetan attend, then Deepa will attend too. If Bharani does not attend, then Akash will not attend. If Deepa does not attend, which of the following is true? Chetan does not attend Akash does not attend either (A) or (B) none of the above
asked Sep 13, 2019 in Numerical Ability gatecse 118 views
1 vote
1 answer
3
80 views
In a running race, Geetha finishes ahead of Shalini and Vani finishes after Aparna. Divya finishes ahead of Aparna. Which of the following is a minimal set of additional information that can determine the winner? Geetha finishes ahead of Divya and Vani finishes ahead of Shalini. Aparna finishes ahead of Shalini. Divya finishes ahead of Geetha. None of the above.
asked Sep 13, 2019 in Numerical Ability gatecse 80 views
4 votes
2 answers
4
148 views
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$
asked Sep 13, 2019 in Graph Theory gatecse 148 views
...