Strategy with regard to how to approach this algorithm?

Question

I was asked this question in a test and I need help with regards to how I should approach the solution, not the actual answer. The question is

You have been given a 7 digit number(with each digit being distinct and 0-9). The number has this property

product of first 3 digits = product of last 3 digits = product of central 3 digits

Identify the middle digit.

Now, I can do this on paper by brute force(trial and error), the product is 72 and digits being

8,1,9,2,4,3,6

Now how do I approach the problem in a no brute force way?

Answer 1

Let the number is: a b c d e f g

So as per the rule(1):

axbxc = cxdxe = exfxg

more over we have(2):

axb = dxe and cxd = fxg

This question can be solved with factorization and little bit of hit/trial. Out of the digits from 1 to 9, 5 and 7 can rejected straight-away since these are prime numbers and would not fit in the above two equations.

The digits 1 to 9 can be factored as:

1 = 1, 2 = 2, 3 = 3, 4 = 2X2, 6 = 2X3, 8 = 2X2X2, 9 = 3X3

After factorization we are now left with total 7 - 2's, 4 - 3's and the number 1. As for rule 2 we are left with only 4 possibilities, these 4 equations can be computed by factorization logic since we know we have overall 7 2's and 4 3's with us.

1: 1X8(2x2x2) = 2X4(2x2)

2: 1X6(3x2) = 3X2

3: 4(2x2)X3 = 6(3x2)X2

4: 9(3x3)X2 = 6(3x2)X3

Skipping 5 and 7 we are left with 7 digits. With above equations we have 4 digits with us and are left with remaining 3 digits which can be tested through hit and trial. For example, if we consider the first case we have:

1X8 = 2X4 and are left with 3,6,9. we have axbxc = cxdxe we can opt c with these 3 options in that case the products would be 24, 48 and 72.

24 cant be correct since for last three digits we are left with are 6,9,4(=216)

48 cant be correct since for last three digits we are left with 3,9,4(=108)

72 could be a valid option since the last three digits in that case would be 3,6,4 (=72)

Answer 2

This question is good to solve with Relational Programming. I think it very clearly lets the programmer see what's going on and how the problem is solved. While it may not be the most efficient way to solve problems, it can still bring desired clarity and handle problems up to a certain size. Consider this small example from Oz:

fun {FindDigits}
   D1 = {Digit}
   D2 = {Digit}
   D3 = {Digit}
   D4 = {Digit} 
   D5 = {Digit}
   D6 = {Digit}
   D7 = {Digit}
   L = [D1 D2 D3] M = [D3 D4 D5] E= [D5 D6 D7] TotL in
   TotL = [D1 D2 D3 D4 D5 D6 D7]
   {Unique TotL} = true
   {ProductList L} = {ProductList M} = {ProductList E}
   TotL
end

(Now this would be possible to parameterize furthermore, but non-optimized to illustrate the point).

Here you first pick 7 digits with a function Digit/0. Then you create three lists, L, M and E consisting of the segments, as well as a total list to return (you could also return the concatenation, but I found this better for illustration).

Then comes the point, you specify relations that have to be intact. First, that the TotL is unique (distinct in your tasks wording). Then the next one, that the segment products have to be equal.

What now happens is that a search is conducted for your answers. This is a depth-first search strategy, but could also be breadth-first, and a solver is called to bring out all solutions. The search strategy is found inside the SolveAll/1 function.

{Browse {SolveAll FindDigits}}

Which in turns returns this list of answers:

[[1 8 9 2 4 3 6] [1 8 9 2 4 6 3] [3 6 4 2 9 1 8] 
 [3 6 4 2 9 8 1] [6 3 4 2 9 1 8] [6 3 4 2 9 8 1] 
 [8 1 9 2 4 3 6] [8 1 9 2 4 6 3]]

At least this way forward is not using brute force. Essentially you are searching for answers here. There might be heuristics that let you find the correct answer sooner (some mathematical magic, perhaps), or you can use genetic algorithms to search the space or other well-known strategies.

Answer 3

Prime factor of distinct digit (if possible)

0 = 0
1 = 1
2 = 2
3 = 3
4 = 2 x 2
5 = 5
6 = 2 x 3
7 = 7
8 = 2 x 2 x 2
9 = 3 x 3

In total: 7 2's + 4 3's + 1 5's + 1 7's

With the fact that When A=B=C, composition of prime factor of A must be same as composition of prime factor of B and that of C, 0 , 5 and 7 are excluded since they have unique prime factor that can never match with the fact.

Hence, 7 2's + 4 3's are left and we have 7 digit (1,2,3,4,6,8,9). As there are 7 digits only, the number is formed by these digits only.

Recall the fact, A, B and C must have same composition of prime factors. This implies that A, B and C have same number of 2's and 3's in their composition. So, we should try to achieve (in total for A and B and C):

1. 9 OR 12 2's AND
2. 6 3's

(Must be product of 3, lower bound is total number of prime factor of all digits, upper bound is lower bound * 2)

Consider point 2 (as it has one possibility), A has 2 3's and same for B and C. To have more number of prime factor in total, we need to put digit in connection digit between two product (third or fifth digit). Extract digits with prime factor 3 into two groups {3,6} and {9} and put digit into connection digit. The only possible way is to put 9 in connection digit and 3,6 on unconnected product. That mean xx9xx36 or 36xx9xx (order of 3,6 is not important)

With this result, we get 9 x middle x connection digit = connection digit x 3 x 6. Thus, middle = (3 x 6) / 9 = 2