4
\$\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\$

3 Answers 3

6
\$\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\$
2
  • 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, 2015 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, 2015 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 ab = abc / 10;
    int a = ab / 10;
    int b = ab % 10;
    int abc_c = abc % 10;
    if (c == abc_c && a != b && b != c && a != c) {
        printf("%d * 3 = %d\n", abc, abc * 3);
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ It's probably worth pointing out that we know the division ccc / 3 will always be exact (because 111 is 3*37 - in fact, that means we could write abc = c * 37)). If that were not the case, we'd need an additional test. \$\endgroup\$ May 12, 2021 at 7:46
0
\$\begingroup\$

I'll ignore the fact that the puzzle can be solved logically, without brute-force search, and concentrate on the code itself.

We're missing an include of <stdio.h> to declare printf().

The comment // your code goes here is unnecessary.

Prefer to define variables with the minimum reasonable scope, and initialise as they are declared. For example,

for (int hun = 0;  hun < 10;  ++hun)

The test for unequal digits is inefficient in the inner loop. We could skip entire outer loops:

    for (int dec = 0;  dec < 10;  ++dec) {
        if (dec == hun) {
            continue;
        }
        for (int unit = 0;  unit < 10;  ++unit) {
            if (unit == dec || unit == hun) {
                continue;
            }

temp_num is a poor name for a variable. The scope and type can show us it's a temporary number, but what the reader needs to know is what it means. I'd name it using the notation of the problem domain, abc. And I'd write ccc rather than final_num.

Prefer to print complete lines (ending in newline), rather than partial (unterminated) lines:

      printf(" Hun %d Dec %d Unit %d\n", hun, dec, unit);

There's no need for the "End of file" message - successful exit is enough to indicate the end of output. And (unlike normal functions) main() can implicitly return success without writing return 0;.

Applying these improvements, we end up with this brute-force program:

#include <stdio.h>

int main(void)
{
    for (int a = 0;  a < 10;  ++a) {
        for (int b = 0;  b < 10;  ++b) {
            if (b == a) {
                /* digits must be distinct */
                continue;
            }
            for (int c = 0;  c < 10;  ++c) {
                if (c == b || c == a) {
                    /* digits must be distinct */
                    continue;
                }
                int abc = a * 100 + b * 10 + c;
                int ccc = c * 100 + c * 10 + c;
                if (abc + abc + abc == ccc) {
                    printf("%d + %d + %d = %d\n", abc, abc, abc, ccc);
                }
            }
        }
    }
}
\$\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.