The Gateway to Computer Science Excellence
+30 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.


$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 _______.

in Algorithms by
edited by | 2.7k views
in sudo code if c[i]=1 is equivalent to if(c[i]==1)

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

'Z' value will loop from 1->2->4->0

Therefore, Z=0 (Answer)

7 Answers

+33 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$.
edited by
you have not incremented "i" in your answer...z becomes 0 at i=2;
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
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?
what is the scope and termination condition of do loop here in the question??????

unable to get do loop scope

@Anup , It is written in Pseudocode which follows Indentation .  it does not use brackets to show blocks. Given question follows pseudocode convention of CLRS. 


yes indentation pattern
+18 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
Answer is 0. By manually iterating through the steps by pencil and paper we can get this answer
edited by
+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
+3 votes

May be this works ...........

+2 votes

this is the algorithm to find  amod n.

here a =2, c =(1011)2 = 11, n=8

hence 211 mod 8 = 0

How can u assume this thing ?

Any Proof ? Which Text Book It From ? @y mint

+2 votes

Initial value $z=1$.

Let's check the values of the binary array $c=[1,0,1,1]$.
When $c[0]=1$ it is $z \leftarrow z^2 = 1$ and $z \leftarrow z\times a = 1\times a =a$

When $c[1]=0$ it is $z \leftarrow z^2 = a^2$ and $z \leftarrow z\times a$ is not evaluated.

When $c[2]=1$ it is $z \leftarrow z^2 = (a^2)^2=a^4$ and $z \leftarrow z\times a = a^4\times a =a^5$

When $c[3]=1$ it is $z \leftarrow z^2 = (a^5)^2=a^{10}$ and $z \leftarrow z\times a = a^{10}\times a =a^{11}$


Note that $(1011)_2=11$ from the binary array $c=[1,0,1,1]$.

So the question reduces to $a^{\text{DecimalValue(Binary Array }c)}\mathrm{~mod~}n$

$\therefore a^{11} \mathrm{~mod~}n = 2^{11}\mathrm{~mod~}8=0$

So the output is $0$.


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
52,345 questions
60,495 answers
95,306 users