Problem in this post is more like a research problem than a puzzle and won't be asked in any interview or written test. So, if you don't want to solve such a puzzle then skip this part and solve the second problem. This problem was part of an R&D project, we are doing with Prof. Nutan Limaye. I and Pritish have been trying this problem for quite some time. Although we have some solutions but optimal solution still seems to be hidden somewhere.
Some definitions:
Depth: Length of the longest path from input to the output.
Problem: Given two numbers in binary form (n bit numbers), can you make a addition circuit using O(n*log(n)) gates in O(1) depth? Only and, or, not gates are allowed. Number of inputs to a gate can be arbitrary large.
No treat for the next puzzle:
2. Does there exist a number of the form 1111.....111 that is divisible by 2097? Explain your answer.
Which treat for the first one?
ReplyDeleteThe title says Mantra treat, doesn't it Prad?
ReplyDeleteeAlso Madan, you should probably mention that the gates can have arbitrary number of inputs.
@Ravi: I forgot to mention that.
ReplyDelete@prad: Isn't is obvious from the title?
soln 2 : i think not possible , when converting binary to decimal it is
ReplyDelete1 + 2 + 4 + 8 + 16 +......
sum of a GP. Which never converges to to 2097 for any n belongs to integer.