3
\$\begingroup\$

A friend gave this puzzle:

Find 3 numbers (say, A B C) such that

\$ABC+ABC+ABC = CCC\$

ABC means \$((A*100) + (B*10) + C)\$. Also, these 3 digits must be distinct.

I wrote a quick code to find out the answer:

int main(void) {
    // your code goes here
    int hun,dec,unit;
    int final_num = 0;
    int temp_num = 0;
    for(hun = 0; hun <10; hun++)
    {
        for(dec = 0; dec < 10; dec++)
        {
            for(unit = 0; unit < 10; unit++)
            {
                // Calculate the number which would be formed with this unit place
                final_num = (unit *100) + (unit * 10) + (unit);

                // Values should not be same
                if((unit!=dec) && (unit != hun) &&( dec != hun))
                {
                    // Number with current combo of ABC
                    temp_num = ((hun * 100) + (dec * 10) + unit) * 3;
                    if(temp_num ==final_num )
                    {
                        printf("Number is %d \n",temp_num);
                        printf(" Hun %d Dec %d Unit %d",hun,dec,unit);
                    }
                }
            }
        }
    }
    printf("\nEnd of File ");
    return 0;
}

And the Answer was 185 (185 + 185 + 185 = 555).

That was very amateur code. Upon thinking, I realized I could have implemented equation \$300A + 30B + 3C = 111C\$. But still couldn't avoid for loop. What could be the better way to implement this? I know only C so I solved it with C.

\$\endgroup\$
5
\$\begingroup\$

I'm sorry, but the best solution to this problem has to be a logic solution, not a code solution. There are only 2 digits that, when multiplied by 3, have the same last digit... 0, and 5. So, 0+0+0 is 0, and 5+5+5 is 15.

Since C cannot be 0, it means that C can only be 5. Now, if C is 5, and we know that there is a 'carry' of 1 in to the tens column, it means we need to find a number other than 5 that when added together 3 times ends in a 4.

There is only one value that does that, 8. 8 + 8 + 8 is 24, and with the carry of 1, we have 25 (and a carry of 2 in to the 100's column).

So, now we need a digit that sums three times to 3, and that's 1.

There is only one possible solution where ABC + ABC + ABC is CCC, and that's 185. It can be deduced using logic alone, and brute-forcing it is overkill.

\$\endgroup\$
  • 1
    \$\begingroup\$ In other words, anything better then brute force requires logically analyzing the algorithm you'd use, which should naturally lead to solving the problem without a single line of code! \$\endgroup\$ – phyrfox May 21 '15 at 15:47
  • \$\begingroup\$ Although, technically, since you've outlined thus answer, someone could conceptually write a program that figures this out programmatically without knowing the solution, by solving for one digit at a time from left to right, with a possible backtracking algorithm in case of partial matches. \$\endgroup\$ – phyrfox May 21 '15 at 15:51
4
\$\begingroup\$

The most stringent condition in the requirements is that the sum will have 3 digits that are all the same. Maybe it's easier to work from this angle. So, you can just use one loop from 1 to 9, form the number, divide by 3, and check the other conditions.

for (int c = 1; c <= 9; ++c) {
    int ccc = 111 * c;
    int abc = ccc / 3;
    int a = abc / 100;
    int b = abc / 10;
    if (abc % 10 == c && a != b && b != c && a != c) {
        printf("%d\n", abc);
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.