edited by
12,133 views
56 votes
56 votes

In the following $C$ program fragment, $j$, $k$, $n$ and TwoLog_n are integer variables, and $A$ is an array of integers. The variable $n$ is initialized to an integer $\geqslant 3$, and TwoLog_n is initialized to the value of $2^*\lceil \log_2(n) \rceil$

for (k = 3;  k <= n; k++)
        A[k] = 0;
for (k = 2; k <= TwoLog_n; k++)
    for (j = k+1; j <= n; j++)
        A[j] = A[j] || (j%k);
for (j = 3; j <= n; j++)
    if (!A[j]) printf("%d", j);

The set of numbers printed by this program fragment is

  1. $\left\{m \mid m \leq n, (\exists i)\left[m=i!\right]\right\}$

  2. $\left\{m \mid m \leq n, (\exists i) \left[m=i^2\right]\right\}$

  3. $\left\{m \mid m \leq n, \text{m is prime} \right\}$

  4. { }

edited by

7 Answers

Best answer
39 votes
39 votes

The nested loop takes all integers from $2$ to $2\ast \log_2 n$, takes all their non-multiples before $n$, and makes the corresponding entry in $A$ as $1$. For example, for $2$, and $n = 10, A[3], A[5], A[7]$, and $A[9] $are made $1$. Similarly for $3, 4, \ldots$ till $2\ast \log n$. So, if any entry $A[p]$ is $0$ means it must be a multiple of $2, 3, .... 2\ast \log_2 n$, which is $\left ( 2 \log n \right )!$ and is greater than $n$. So, for no index $p$, $A[p]$ will be $0$. So, the answer is D

Suppose the line

A[j] = A[j] || (j%k);

is replaced with

A[j] = A[j] || !(j%k);

Now, the nested loop takes all integers from $2$ to $\log_2 n$, takes all their multiples before $n$, and makes the corresponding entry in $A$ as $1$. For example, for $2$, and $n = 10, A[4], A[6], A[8]$ and $A[10]$ are made $1$. Similarly for $3, 4, ...$ till $2\ast \log n$ . So, for all non-prime indices of $A$, we will have a $1$, and for prime indices, we have a $0$. And we print $j$ if $A[j]$ is $0$ meaning $j$ is prime. 

edited by
7 votes
7 votes

Lets' divide this code to 3 parts.

for (k = 3;  k <= n; k++)
    A[k] = 0;

Above code is assigning value $0$ to array $A$ from index $3$ till $n$. It’s interesting to note that $A[0], A[1], A[2]$ could be garbage values or some integers, but for this particular code, we dont’ need to worry about them. Since, we are operating on index $\geq 3$. 

for (j = 3; j <= n; j++)
    if (!A[j]) printf("%d", j);

We are just printing the values of index $j$ after processing over the array $A[j\geq3]$. Hence above two codes are not contributing to operations over $A$, rather assigning and printing. 

for (k = 2; k <= TwoLog_n; k++)
    for (j = k+1; j <= n; j++)
        A[j] = A[j] || (j%k);

We need to analyze third line of this code. $||$ is logical OR operator which gives $True$ when atleast one value is $True$. Hence co-domain of $A[p]$ will be $\{0,1\}$. Now $A[j] == 1$ when $A[j]==1$ or $j\%k \ != 0$ (inclusive OR). $A[j]==1$ won’t reveal us with much information regarding how $A[j]$ getting updated, so we need to analyze $j\%k$. 

$\text{if }j\%k ==0 \text{ then }\exists_{m \in \{1,2,\dots, \lfloor\frac{n}{k}\rfloor\}} \ j = =mk$ 

$\implies A[j] == 1 \text{ when j is not a multiple of k}$

when,

$k=2$, then $\forall_{n \geq j \geq 2+1} \ (2  \bcancel{|} j \implies \ A[j] == 1)$

$k=3$, then $\forall_{n \geq j \geq 3+1} \ (3  \bcancel{|} j \implies \ A[j] == 1)$

Its’ important to recall that we are updating the same array $A$ at $i^{th}$ index in every successive iteration of loop. Hence when $k=p$ then $\forall_{n \geq j \geq 3} \ (\exists_{m \in \{1,2,\dots,p\}} \ m \ \bcancel{|} \ j  \implies  A[j]==1)$. Its’ contrapositive can be written as $\forall_{n \geq j \geq 3} \  (A[j]==0 \implies  \forall_{m \in \{1,2,\dots,p\}} \ m \ | \ j )$.

This says for a value of $j$, if $A[j]==0$  then $j$ should be divisible by every integer from $1$ to $p$. This means that $j$ should be a multiple of every integer from $1$ to $p$, hence $j = p!$ and $p$ goes till $2*\lceil\log_2{n}\rceil$. 

After exiting nested loops, the $j$ value(s) for which $A[j]==0$ should be multiple of $(2*\lceil\log_2{n}\rceil)!$. But first we need to check if $(2*\lceil\log_2{n}\rceil)! \leq n$ ($\textbf{why?}$), because $j \leq n$. 

$$\begin{align}(2*\lceil\log_2{n}\rceil)! &\qquad n\cr \log {2*\lceil\log_2{n}\rceil!} &\qquad \log_2{n} \tag{log both sides} \cr 2*\log_2{n}\log_2{2*\log_2{n}} &\qquad \log_2{n}\end{align}$$

Clearly $(2*\lceil\log_2{n}\rceil)! > n$, hence for no value of $j \leq n$, $A[j]==0$. So no $j$ value will be printed in the last for-loop $or$ it would be an empty set.

Hence, $\textbf{Option D}$.

Answer:

Related questions

27 votes
27 votes
3 answers
1
Kathleen asked Sep 16, 2014
10,024 views
Consider the following $C$ function.For large values of $y$, the return value of the function $f$ best approximatesfloat f,(float x, int y) { float p, s; int i; for (s=1,...
50 votes
50 votes
11 answers
4
Kathleen asked Sep 17, 2014
14,114 views
The following are the starting and ending times of activities $A, B, C, D, E, F, G$ and $H$ respectively in chronological order: $“a_s \: b_s \: c_s \: a_e \: d_s \: c_...