Feature #10: Decode a Message
Explore how to decode a message digest created by arithmetic operations on integers. Learn to apply +, -, *, and / operators under specific rules to determine if a target message digest can be formed. Understand the use of recursion and depth-first search to test all combinations. This lesson will help you develop problem-solving strategies useful for coding interviews involving arithmetic expressions and backtracking algorithms.
We'll cover the following...
Description
In this feature, we will reverse a message digest function. The message digest function applies a subset of the operators +, -, *, and / along with some parenthesization to individual digits in the message and converts the subset into the message digest. The message will consist of four integers, each in the range [1, 9]. The message digest is also an integer.
Note: It is also possible that no combination of these operations may lead to a message digest.
We will be given the array of integers and the message digest. We will be restricted by the following rules:
-
The division operator
/represents real division, not integer division. -
We cannot use
-as a unary operator. Every operation is carried out between two numbers. -
We cannot concatenate numbers together. For example, if
message...