The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+7 votes

A finite sequence of bits is represented as a list with values from the set $\{0,1\}$. For example, $[0,1,0]$, $[1,0,1,1]$, . . . .
[ ] denotes the empty list, and $[b]$ is the list consisting of one bit $b$. The function $length(l)$ returns the length (number of bits) in the list $l$. For a nonempty list $l$, $head(l)$ returns the first element of $l$, and $tail(l)$ returns the list obtained by removing the first element from $l$. The operator $++$ denotes list concatenation.
For example:

  • $head([0,1,0]) = 0, tail([0,1,0]) = [1,0]$,
  • $head([1]) = 1, tail([1]) = $ [ ], and
  • $[0,1,0]++[1] = [0,1,0,1]$.

Consider the following functions:
$op$ takes as input two bits and returns a bit.

if (a = b) return(0)
else return(1)

$mystery1$ takes as input two lists and returns a list.

if (length(s) != length(t)) then return(t)
else if (length(s) = 0) then return(s)
else return([op(head(s),head(t))] ++ mystery1(tail(s),tail(t)))

$mystery2$ takes as input two lists and outputs a list.

if (length(t) = 0) then return(s)
else return( mystery1(mystery2(s,tail(t)),mystery2(s,tail(t))))
  1. Suppose $s=t=110100100$. What are the first two bits of $mystery2(s,t)$?
in Algorithms by Veteran (100k points)
edited by | 255 views
I think its ans should be - 000000000

Here mystery1 returns xor of two binary string if both has same length.
wouldn't mystery2 always return 0 if s == t and len(s) >= 1, because it will return mystery1(x,x) which is 00......len(s) times because mystery1 calculates the list xor, for mystery2, x =  mystery2(s,tail(t))

1 Answer

+9 votes
Best answer

Here, the $op$ function takes two bits as input and outputs their $\text{XOR} (\oplus).$

Let $x_1$ and $x_2$ be the two input bits in the function $op$.

Then, the output is $x_3$ s.t. $\boxed{x_3 = x_1 \hspace{0.1cm} \oplus \hspace{0.1cm} x_2 }\quad \rightarrow \text{(output of op function)}$

Now, the mystery $1$ function takes two lists $s$ and $t$ as input and outputs another list $u$  (say) such that

$\boxed{u = s \oplus  t} \quad \rightarrow \text{(output of mystery 1 function)}$

and the output of mystery $2$ function is 

$$u =\underset{2 ^{\text{length}(t)} \text{times}}{\underbrace{ s \oplus s \oplus s \oplus s \ldots \oplus s}} $$

  1. Taking $\text{XOR}$ of $s,$ $2^{\text{length}(t) }$ times does not change the $\text{length}(s)$. So, our answer will be $\text{length}(s) .$
  2. In this problem the first two bits of length $s$ are $11$, so taking the $\text{XOR}$ of $1,$ even number of times gives the output $0$. So, our answer is $00$. 
by Loyal (9.6k points)
selected by
Why isn't the answer 000000000?
They asked only for the first two bits that's why

@Kushagra Chatterjee In output of mystery2 function, I think, it should be $2^{length(t)}-1$ because I am getting these many mystery1 calls for particular mystery2(s,t) by taking some sample inputs like s=01,t=101 or s=010,t=101...please check..


Written mys inplace of mystery


@Kushagra Chatterjee here , string $01$ are of $2^{3}=8$ times but XOR operation is done $2^{3}-1=7$ times. right ?

I am saying it because you have written "Taking XOR of s,  $2^{length(t)}$ times does not change.." in next line. Please correct me if I am wrong.



yes ur logic correct.

But check last picture of @Kushagra 

I think it has small mistake

It calls mystery2(110,110) at first

and it returns (mystery1(10),10) at very first call (Even before calling mystery1() for the first time)

Isnot it??


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
50,092 questions
55,322 answers
86,220 users