Tag Info

3

Using Trie Data Structure, you can solve this problem in $O(m + n)$ if we know that values are computer integers (e.g. all 32-bit or 64-bit values). Let say we know that all integers in $A$ are 32-bit values. Use the following steps: Create an empty trie. Every node of trie may contains at most two children for 0 and 1 bits. Insert all values in $A$ into ...

2

This question can be reduced to the exact cover problem which is NP-Complete. A typical method for solving the exact cover problem is known as Algorithm X. Consider the set of choices you have: For each tetris piece of $4$ units, you can select an orientation and a location to place it on the board. For each choice, the piece will cover $4$ squares on the ...

1

In general Warnsdorff's rule is just a heuristic that guides the search. It is still possible that the search hits a dead-end and we are forced to backtrack. So let us consider the $n \times n$ chessboard now. Warnsdorff's rule (nor any other method) won't find a solution for $n < 5$ as a solution exists precisely when $n \geq 5$. Given that $n \geq 5$, ...

Only top voted, non community-wiki answers of a minimum length are eligible