//-------------------------------------------------------------------
// 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 <stdio.h>

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;
}