2.2k views

Suppose $c = \langle c, \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 _______.

edited | 2.2k views
0
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 ??

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 = 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 = 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$.
by Active (2.3k points)
edited
+4
you have not incremented "i" in your answer...z becomes 0 at i=2;
+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
+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=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
+2

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

PFA from CLRS  0
yes indentation pattern

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
by Boss (23.8k points)
Answer is 0. By manually iterating through the steps by pencil and paper we can get this answer
by Junior (657 points)
edited
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
by Active (2.7k points)

May be this works ........... by Junior (539 points)

this is the algorithm to find  amod n.

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

hence 211 mod 8 = 0

by Active (1.4k points)
+1
How can u assume this thing ?
0

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

Initial value $z=1$.

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

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

When $c=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=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$.

by Active (3.2k points)