//------------------------------------------------------------------- // enigma1343.c (c) 2005 by Charles Petzold (www.charlespetzold.com) // // "Digital Dividend", New Scientist, 4 June 2005, page 28. // // Find the largest number whose digits are all different (and non-zero) // and which is divisible by each of its digits. // // This problem practically cries out for a brute-force approach. // You basically start with the largest number whose digits are all // different and non-zero, test it, and decrement. Lather, rinse, // repeat. // // The largest number whose digits are all different and non-zero // is 987,654,321. However, this number is obviously not divisible by // all its digits. It's not divisible by 2, for example. // // MOREOVER -- and this is the important revelation that dramatically // cuts the job down in size -- any number that is divisible by both 2 // and 5 is also divisible by 10, which means that the least-significant // digit is 0. Therefore, the solution cannot contain both 2 and 5, // which means that it cannot be a 9-digit number. // // Also, if the number does contain a 5, then 5 must be the // least-significant digit. // // So, let's instead start with the largest 8-digit number whose digits // are all different and non-zero, and see if the program finishes in a // reasonable amount of time. (It takes less than a minute.) //------------------------------------------------------------------- #include int main(void) { int Number, i, Test, Digits[10], Digit; for (Number = 98764321; Number > 0; Number--) { // Zero out the array used to determine if all the digits // are unique. for (i = 0; i < 10; i++) Digits[i] = 0; // Copy the number into another int for stripping out the // digits. Test = Number; while (Test > 0) { // Obtain the least-significant digit. If it's zero, // we're not interested in the number. if (0 == (Digit = Test % 10)) break; // If that digit is already in the array, we're not // interested either. if (Digits[Digit] == 1) break; // If the number is not divisible by that digit, // we just don't care. if (Number % Digit != 0) break; // So far, so good. Set that element of the array so // we know we have that digit and won't duplicate it. Digits[Digit] = 1; // Divide the Test integer by ten to have access to // the next less-significant digit. Test /= 10; } // If the number passed all the tests in the while loop without // prematurely exiting, we have a winner! if (Test == 0) break; } printf("%i\n", Number); return 0; }