fork download
  1. public class Q17587532
  2. {
  3. static int[] GetDigitProducts( int max )
  4. {
  5. int sweep = 1;
  6. var results = new int[max+1];
  7. for( int i = 1; i <= 9; ++i ) results[i] = i;
  8. // loop invariant: all values up to sweep * 10 are filled in
  9. while (true) {
  10. int prior = results[sweep];
  11. if (prior > 0) {
  12. for( int j = 1; j <= 9; ++j ) {
  13. int k = sweep * 10 + j; // <-- the key, generating number from digits is much faster than decomposing number into digits
  14. if (k > max) return results;
  15. results[k] = prior * j;
  16. // loop invariant: all values up to k are filled in
  17. }
  18. }
  19. ++sweep;
  20. }
  21. }
  22.  
  23. static void VisitDigitProductsImpl(int min, int max, System.Action<int, int> visitor, int build_n, int build_ndp)
  24. {
  25. if (build_n >= min && build_n <= max) visitor(build_n, build_ndp);
  26.  
  27. // bound
  28. int build_n_min = build_n;
  29. int build_n_max = build_n;
  30.  
  31. do {
  32. build_n_min *= 10;
  33. build_n_max *= 10;
  34. build_n_max += 9;
  35.  
  36. // prune
  37. if (build_n_min > max) return;
  38. } while (build_n_max < min);
  39.  
  40. int next_n = build_n * 10;
  41. int next_ndp = 0;
  42. // branch
  43. for( int i = 1; i <= 9; ++i ) {
  44. next_n++;
  45. next_ndp += build_ndp;
  46. VisitDigitProductsImpl(min, max, visitor, next_n, next_ndp);
  47. }
  48.  
  49. }
  50.  
  51. static void VisitDigitProducts(int min, int max, System.Action<int, int> visitor)
  52. {
  53. for( int i = 1; i <= 9; ++i )
  54. VisitDigitProductsImpl(min, max, visitor, i, i);
  55. }
  56.  
  57. public static void Main()
  58. {
  59. int min = 818304;
  60. int max = 998765;
  61. int[] products = GetDigitProducts(max);
  62.  
  63. int matches = 0, mismatches = 0;
  64.  
  65. VisitDigitProducts(min, max, delegate (int n, int ndp) { if (ndp == products[n]) matches++; else mismatches++; products[n] = -1; });
  66.  
  67. System.Console.WriteLine(matches.ToString() + " matches and " + mismatches.ToString() + " mismatches and " + (max-min+1 - matches - mismatches).ToString() + " unvisited");
  68.  
  69. int unvisited = 0;
  70. for( int n = min; n <= max; n++ ) if (products[n] > 0) ++unvisited;
  71.  
  72. System.Console.WriteLine(unvisited.ToString() + " unvisited and non-zero");
  73.  
  74. }
  75. }
Success #stdin #stdout 0.04s 37864KB
stdin
Standard input is empty
stdout
111911 matches and 0 mismatches and 68551 unvisited
0 unvisited and non-zero