then how can u write if(c[i]=1) in sudo code ??

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+26 votes

Suppose $c = \langle c[0], \dots, c[k-1]\rangle$ is an array of length $k$, where all the entries are from the set $\{0, 1\}$. For any positive integers $a \text{ and } n$, consider the following pseudocode.

DOSOMETHING (*c, a, n)*

$z \leftarrow 1$

for $i \leftarrow 0 \text{ to } k-1$

do $z \leftarrow z^2 \text{ mod } n$

if *c*[i]=1

then $z \leftarrow (z \times a) \text{ mod } n$

return z

If $k=4, c = \langle 1, 0, 1, 1 \rangle , a = 2, \text{ and } n=8$, then the output of DOSOMETHING(*c, a, n)* is _______.

+27 votes

Best answer

Initially $k = 4$, $c = [1, 0, 1, 1]$, $a = 2$, $n = 8$.

Now let's iterate through the function step by step :

$z = 1$ (at the start of do-something)

$i = 0$ (start of external for loop)

In the do loop

$z = 1*1 % 8 = 1$ (non zero value so considered as true and continue)

$c[0] = 1$, so in the if clause, $z = 1*2 \% 8 = 2$

In the do loop

$z = 2*2 \% 8 = 4$ (since now $z = 2$) (non zero value so considered as true and continue)

$c[0] = 1$, so in the if clause, $z = 4*2 \% 8 = 0$

Now no need to check further :

Reason : All the operations that update $Z$ are multiplicative operations and hence the value of $Z$ will never change from $0$.

Now let's iterate through the function step by step :

$z = 1$ (at the start of do-something)

$i = 0$ (start of external for loop)

In the do loop

$z = 1*1 % 8 = 1$ (non zero value so considered as true and continue)

$c[0] = 1$, so in the if clause, $z = 1*2 \% 8 = 2$

In the do loop

$z = 2*2 \% 8 = 4$ (since now $z = 2$) (non zero value so considered as true and continue)

$c[0] = 1$, so in the if clause, $z = 4*2 \% 8 = 0$

Now no need to check further :

Reason : All the operations that update $Z$ are multiplicative operations and hence the value of $Z$ will never change from $0$.

+3

There are no bracket so how scope of for loop is more than 1 line ?

Do we hv to follow structure pattern in this type of code

Do we hv to follow structure pattern in this type of code

+6

I think answer is having some typeo.In the second iteration we will never enter if and z remains 4.Now in third iteration,it becomes 16 mod 8 and thus we get 0 and it remains the same for upcoming iterations.But in answer its entering into if on second iteration,which is not possible as c[1]=0.Someone please check it once?

0

what is the scope and termination condition of do loop here in the question??????

unable to get do loop scope

unable to get do loop scope

+14 votes

z=1 k = 4, c = [1, 0, 1, 1], a = 2, n = 8

now if we analyze the code we will get table like this Hence Ans is 0.

i |
z |

0 | 2 |

1 | 4 |

2 | 0 |

3 | 0 |

+6 votes

+3 votes

we can do it mentally , at one stage value of z will be zero , beyond that , for any value of K it will be 0 only.

Ans :0

Ans :0

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 584
- Exam Queries 572
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,121 questions

53,242 answers

184,708 comments

70,481 users