fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
111911 matches and 0 mismatches and 68551 unvisited
0 unvisited and non-zero
https://ideone.com/AIal1L
language:
C# (gmcs 5.20.1)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!