in Algorithms edited by
12,072 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. { }

in Algorithms edited by
12.1k views

4 Comments

In geeksforgeeks ans is given as B.

explaination given as :

// Initialize all values as 0

for (k = 3; k < = n; k++)

    A[k] = 0;

  

for (k = 2; k < = TwoLog_n; k++)

    for (j = k + 1; j < = n; j++)

        // If k divides j, then A[j] is 

        // set as 0, else non-zero

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

  

// Print all numbers where A[j] is 0

for (j = 3; j < = n; j++)

    if (!A[j]) 

        printf("%d", j);

0
0
reshown by
Here the inner loop runs till n. Every inner iteration changes contents of A. For first inner iteration A is 1 for even or 0 for odd places. But now after first inner iteration, second outer iteration comes which starts from k+1, content of A are changed again, previous inner iteration after 1 time become meaningless. So, important thing is matching first outer iteration with first inner iteration ONLY. i think TWOLOGN is just to make confuse us
0
0
It is whether ceil function or floor function in log2(n) becz in made easy pyq book they have made floor function and here in question ceil function is used ?
0
0

7 Answers

39 votes
39 votes
Best answer

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
by

4 Comments

@Arjun Sir,

And we print i if A[j] is 0 meaning j is prime. 

 Isn’t we printing j if A[j] is 0.

1
1
Thats a typo – fixed now.
1
1
@Arjun Sir, wont we get 1 for all numbers no matter prime or not as it is modulo...(it will definetly give some remainder) ex:5%3 =2 5%2=3...please correct me..where i am going wrong
0
0
40 votes
40 votes

take n=3 So TwoLog_n=4 . Suppose A[4]

2 Comments

nice answer!!.
0
0
how can we say, all other input also give same ans??:(
2
2
9 votes
9 votes
Answer: D

The code sets 1 at all array index after A[2].

Ref: http://ideone.com/2bsRHY

1 comment

Yes. I have updated the answer :)
2
2
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}$.

1 comment

@Sachin Mittal 1 Sir, can you please review this once. 

0
0
Answer:

Related questions