Programming Problems: Arranging digits
 

 

Problem:
Insert + or - sign anywhere between the digits 123456789 in such a way that the expression evaluates to 100. The condition is that the order of the digits must not be changed.
e.g.: 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100

Programming Problem:
Write a program in C/C++/Java which outputs all possible solutions of the above problem.

      Before reading the solution, please try to solve the problem on your own as it can improve your logical and analytical skills a lot. Also, readers are requested to find at least 4 solutions using paper and pencil so as to understand deeply about the problem.


Solution:
Analysis of the problem:

      The problem may seem very easy at first sight. But we will understand that it is not so. Actually solving this problem become very difficult for some one who has not seen problems pertaining to this specific class. Whenever we try to find a solution for the problem using paper and pencil, we may only find some simple solutions, and may not be able to get all the solutions.

Also after finding a number of solutions, we may not know whether any other solution exits or not.

      Thus in essence, it is difficult to list all the solutions of the problem using pencil and paper. So we will use a computer to solve the problem. We have to write a program for this.

Solution:
Let us illustrate the basic problem statement in a more computer friendly way:

_1 _ 2_ 3 _4 _5 _6 _7 _8 _9

      We must either fill the blanks above with +/- or we must remove the blanks such that the digits on either side of the blank combine to form a single number.

E.g.: _ 1 _ 2_ 3 _4 _5 _6 _7 _8 _9

becomes

123 - 4 + 5 + 67 - 89

      Then we must evaluate the resulting expression to find whether it is equal to 100. If it equals 100, we may output the expression.
Now, there are three possible ways we may deal with a blank:
(1) Remove the blank
(2) Put a + sign in the blank
(3) Put a - sign in the blank


We may denote these three cases using three numbers:
 

Removing blank

0

Replace blank with +

1

Replace blank with -

2


      We can see that there are 9 blanks altogether. So we can state the problem as filling these blanks using any of these three numbers and then executing the expression accordingly.
E.g.:
0 1 1 2 2 3 0 4 1 5 1 6 1 7 2 8 1 9
becomes
1 + 2 -34 + 5 + 6 +7 – 8 + 9
which calculates to -12 (hence this is not a solution of the problem)

So when we write a program, we must write it in such a way that it can find all the permutations of the three cases in all the blanks. Three cases means 0,1, and 2

number of blanks = 9

      The program must find all permutations of 0,1 and 2 for 9 digits, and use each of these permutation to construct the expression and find if it equal to 100.

      The easiest way to do this is consider 0,1 and 2 as the digits of a base 3 number (Eg:102,210,122210 etc..........) an find all base three up to a digit i.e. we have to find base 3 numbers from 000000000 to 222222222 i.e. in base 10 from 0 to 19682 (i.e. 39-1)


The C source code for getting all the solutions of the problem is given below:
 

#include<stdio.h>
#include<conio.h>
// This function is used to generate number between 0 and 2
int findnumber(int i,int j)
{
    int k;
    int n;
    for(k = 0; k < j; k++)
    {
        n = i % 3;
        i = i / 3;
    }
    return n;
}
void main()
{
    int i, j, k, current, result, operation;
    clrscr();
    for(i = 0; i < 19683; i++)
    {
        if(i%3 == 0)
            continue;
        current = 0;
        result = 0;
        for(j = 1; j < 10; j++)
        {
            k = findnumber(i,j);
            if(k==0)
            {
                current = current * 10 + j;
            }
            else
            {
                result = result + (operation == 1 ? current : -current);
                current = j;
                operation = k;
            }
        }
        result = result + (operation == 1 ? current : -current);
        if(result == 100)
        {
            for(j = 1; j < 10; j++)
            {
                k = findnumber(i,j);
                if(k==0)
                    printf("%d",j);
                else
                    printf("%c%d",k==1?'+':'-',j);
            }
            printf("\n");
        }
    }
    getch();
}
 

The source code can also be downloaded from the Downloads section

 

Trace the source code to understand its working in detail.

The solutions are listed below:

 

+ 123 - 45 - 67 + 89
+ 12 - 3 - 4 + 5 - 6 + 7 + 89
+ 12 + 3 + 4 + 5 - 6 - 7 + 89
+ 123 + 4 - 5 + 67 - 89
- 1 + 2 - 3 + 4 + 5 + 6 + 78 + 9
+ 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
+ 12 + 3 - 4 + 5 + 67 + 8 + 9
+ 1 + 23 - 4 + 56 + 7 + 8 + 9
+ 1 + 2 + 34 - 5 + 67 - 8 + 9
+ 1 + 23 - 4 + 5 + 6 + 78 - 9
+ 123 + 45 - 67 + 8 - 9
+ 123 - 4 - 5 - 6 - 7 + 8 - 9

 

Author: Niyaz PK

 

 

All Rights Reserved © 2007 Hoozi