public class Q17587532
{
static int[] GetDigitProducts( int max )
{
int sweep = 1;
var results = new int[max+1];
for( int i = 1; i <= 9; ++i ) results[i] = i;
// loop invariant: all values up to sweep * 10 are filled in
while (true) {
int prior = results[sweep];
if (prior > 0) {
for( int j = 1; j <= 9; ++j ) {
int k = sweep * 10 + j; // <-- the key, generating number from digits is much faster than decomposing number into digits
if (k > max) return results;
results[k] = prior * j;
// loop invariant: all values up to k are filled in
}
}
++sweep;
}
}
static void VisitDigitProductsImpl(int min, int max, System.Action<int, int> visitor, int build_n, int build_ndp)
{
if (build_n >= min && build_n <= max) visitor(build_n, build_ndp);
// bound
int build_n_min = build_n;
int build_n_max = build_n;
do {
build_n_min *= 10;
build_n_max *= 10;
build_n_max += 9;
// prune
if (build_n_min > max) return;
} while (build_n_max < min);
int next_n = build_n * 10;
int next_ndp = 0;
// branch
for( int i = 1; i <= 9; ++i ) {
next_n++;
next_ndp += build_ndp;
VisitDigitProductsImpl(min, max, visitor, next_n, next_ndp);
}
}
static void VisitDigitProducts(int min, int max, System.Action<int, int> visitor)
{
for( int i = 1; i <= 9; ++i )
VisitDigitProductsImpl(min, max, visitor, i, i);
}
public static void Main()
{
int min = 818304;
int max = 998765;
int[] products = GetDigitProducts(max);
int matches = 0, mismatches = 0;
VisitDigitProducts(min, max, delegate (int n, int ndp) { if (ndp == products[n]) matches++; else mismatches++; products[n] = -1; });
System.Console.WriteLine(matches.ToString() + " matches and " + mismatches.ToString() + " mismatches and " + (max-min+1 - matches - mismatches).ToString() + " unvisited");
int unvisited = 0;
for( int n = min; n <= max; n++ ) if (products[n] > 0) ++unvisited;
System.Console.WriteLine(unvisited.ToString() + " unvisited and non-zero");
}
}
cHVibGljIGNsYXNzIFExNzU4NzUzMgp7CiAgICBzdGF0aWMgaW50W10gR2V0RGlnaXRQcm9kdWN0cyggaW50IG1heCApCiAgICB7CiAgICAgICAgaW50IHN3ZWVwID0gMTsKICAgICAgICB2YXIgcmVzdWx0cyA9IG5ldyBpbnRbbWF4KzFdOwogICAgICAgIGZvciggaW50IGkgPSAxOyBpIDw9IDk7ICsraSApIHJlc3VsdHNbaV0gPSBpOwogICAgICAgIC8vIGxvb3AgaW52YXJpYW50OiBhbGwgdmFsdWVzIHVwIHRvIHN3ZWVwICogMTAgYXJlIGZpbGxlZCBpbgogICAgICAgIHdoaWxlICh0cnVlKSB7CiAgICAgICAgICAgIGludCBwcmlvciA9IHJlc3VsdHNbc3dlZXBdOwogICAgICAgICAgICBpZiAocHJpb3IgPiAwKSB7CiAgICAgICAgICAgICAgICBmb3IoIGludCBqID0gMTsgaiA8PSA5OyArK2ogKSB7CiAgICAgICAgICAgICAgICAgICAgaW50IGsgPSBzd2VlcCAqIDEwICsgajsgLy8gPC0tIHRoZSBrZXksIGdlbmVyYXRpbmcgbnVtYmVyIGZyb20gZGlnaXRzIGlzIG11Y2ggZmFzdGVyIHRoYW4gZGVjb21wb3NpbmcgbnVtYmVyIGludG8gZGlnaXRzCiAgICAgICAgICAgICAgICAgICAgaWYgKGsgPiBtYXgpIHJldHVybiByZXN1bHRzOwogICAgICAgICAgICAgICAgICAgIHJlc3VsdHNba10gPSBwcmlvciAqIGo7CiAgICAgICAgICAgICAgICAgICAgLy8gbG9vcCBpbnZhcmlhbnQ6IGFsbCB2YWx1ZXMgdXAgdG8gayBhcmUgZmlsbGVkIGluCiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgKytzd2VlcDsKICAgICAgICB9CiAgICB9CiAgICAKICAgIHN0YXRpYyB2b2lkIFZpc2l0RGlnaXRQcm9kdWN0c0ltcGwoaW50IG1pbiwgaW50IG1heCwgU3lzdGVtLkFjdGlvbjxpbnQsIGludD4gdmlzaXRvciwgaW50IGJ1aWxkX24sIGludCBidWlsZF9uZHApCiAgICB7CiAgICAgICAgaWYgKGJ1aWxkX24gPj0gbWluICYmIGJ1aWxkX24gPD0gbWF4KSB2aXNpdG9yKGJ1aWxkX24sIGJ1aWxkX25kcCk7CiAgICAgICAgCiAgICAgICAgLy8gYm91bmQKICAgICAgICBpbnQgYnVpbGRfbl9taW4gPSBidWlsZF9uOwogICAgICAgIGludCBidWlsZF9uX21heCA9IGJ1aWxkX247CiAgICAgICAgCiAgICAgICAgZG8gewogICAgICAgICAgICBidWlsZF9uX21pbiAqPSAxMDsKICAgICAgICAgICAgYnVpbGRfbl9tYXggKj0gMTA7CiAgICAgICAgICAgIGJ1aWxkX25fbWF4ICs9ICA5OwogICAgICAgICAgICAKICAgICAgICAgICAgLy8gcHJ1bmUKICAgICAgICAgICAgaWYgKGJ1aWxkX25fbWluID4gbWF4KSByZXR1cm47CiAgICAgICAgfSB3aGlsZSAoYnVpbGRfbl9tYXggPCBtaW4pOwogICAgICAgIAogICAgICAgIGludCBuZXh0X24gPSBidWlsZF9uICogMTA7CiAgICAgICAgaW50IG5leHRfbmRwID0gMDsKICAgICAgICAvLyBicmFuY2gKICAgICAgICBmb3IoIGludCBpID0gMTsgaSA8PSA5OyArK2kgKSB7CiAgICAgICAgICAgIG5leHRfbisrOwogICAgICAgICAgICBuZXh0X25kcCArPSBidWlsZF9uZHA7CiAgICAgICAgICAgIFZpc2l0RGlnaXRQcm9kdWN0c0ltcGwobWluLCBtYXgsIHZpc2l0b3IsIG5leHRfbiwgbmV4dF9uZHApOwogICAgICAgIH0KICAgICAgICAKICAgIH0KICAgIAogICAgc3RhdGljIHZvaWQgVmlzaXREaWdpdFByb2R1Y3RzKGludCBtaW4sIGludCBtYXgsIFN5c3RlbS5BY3Rpb248aW50LCBpbnQ+IHZpc2l0b3IpCiAgICB7CiAgICAgICAgZm9yKCBpbnQgaSA9IDE7IGkgPD0gOTsgKytpICkKICAgICAgICAgICAgVmlzaXREaWdpdFByb2R1Y3RzSW1wbChtaW4sIG1heCwgdmlzaXRvciwgaSwgaSk7CiAgICB9CiAgICAKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBNYWluKCkKICAgIHsKICAgICAgICBpbnQgbWluID0gODE4MzA0OwogICAgICAgIGludCBtYXggPSA5OTg3NjU7CiAgICAgICAgaW50W10gcHJvZHVjdHMgPSBHZXREaWdpdFByb2R1Y3RzKG1heCk7CiAgICAgICAgCiAgICAgICAgaW50IG1hdGNoZXMgPSAwLCBtaXNtYXRjaGVzID0gMDsKICAgICAgICAKICAgICAgICBWaXNpdERpZ2l0UHJvZHVjdHMobWluLCBtYXgsIGRlbGVnYXRlIChpbnQgbiwgaW50IG5kcCkgeyBpZiAobmRwID09IHByb2R1Y3RzW25dKSBtYXRjaGVzKys7IGVsc2UgbWlzbWF0Y2hlcysrOyBwcm9kdWN0c1tuXSA9IC0xOyB9KTsKCiAgICAgICAgU3lzdGVtLkNvbnNvbGUuV3JpdGVMaW5lKG1hdGNoZXMuVG9TdHJpbmcoKSArICIgbWF0Y2hlcyBhbmQgIiArIG1pc21hdGNoZXMuVG9TdHJpbmcoKSArICIgbWlzbWF0Y2hlcyBhbmQgIiArIChtYXgtbWluKzEgLSBtYXRjaGVzIC0gbWlzbWF0Y2hlcykuVG9TdHJpbmcoKSArICIgdW52aXNpdGVkIik7CiAgICAgICAgCiAgICAgICAgaW50IHVudmlzaXRlZCA9IDA7ICAgICAgICAKICAgICAgICBmb3IoIGludCBuID0gbWluOyBuIDw9IG1heDsgbisrICkgaWYgKHByb2R1Y3RzW25dID4gMCkgKyt1bnZpc2l0ZWQ7CiAgICAgICAgCiAgICAgICAgU3lzdGVtLkNvbnNvbGUuV3JpdGVMaW5lKHVudmlzaXRlZC5Ub1N0cmluZygpICsgIiB1bnZpc2l0ZWQgYW5kIG5vbi16ZXJvIik7CgogICAgfQp9