Problem 32: Pandigitale Produkte

Gesucht ist die Summe aller Produkte, deren Gleichungen pandigital von 1 bis 9 sind! Jedes Produkt darf dabei nur einmal auftreten. [das englische Original]

Um die Lösungen dieses Problem einzugrenzen, habe ich die möglichen Wertebereiche betrachtet und dabei die Grenzen geschlussfolgert. Es wird immer eine Gleichung in der Form x * y = z angenommen, wobei alle 3 Zahlen zusammen nicht mehr als 9 Ziffern enthalten können:

  1. Obergrenze: Alle gesuchten Produkte müssen kleiner als 10.000 sein, da bereits für z = 10.000 für x und y nur 4 Ziffern übrig bleiben, was nicht lösbar ist.
  2. Untergrenze: Alle gesuchten Produkte müssen größer als 999 sein, da für alle Produkte kleiner 1.000 mehr als 5 Ziffern für x und y benutzt werden müssen, was ebenfalls nicht lösbar ist.
  3. Aus 1. und 2. folgt für die Werte von x ein Bereich von 1 bis 9.999 und für y von x bis 9.999.

Damit kann man mit den folgenden beiden Schleifen das Problem lösen:

@Override
public String solve() {
   ArrayList< Integer > products = new ArrayList< Integer >();
 
   for( int x=1; x<9999; x++ ) {
      for( int y=x; y<9999; y++ ) {
         int z = x * y;
         if( isPandigitalIdentity( x, y, z ) ) {
            IO.debug( "found: " + x + " x " + y + " = " + z );
            if( !products.contains( z ) ) {
               IO.debugln( " => new" );
               products.add( z );
            } else {
               IO.debugln( " => known" );
            }
         }
      }
   }

   int result = 0;

   for( int p : products ) {
      result += p;
   }
 
   return IO.i2s( result );
}

Um die drei Teile der Gleichung auf Pandigitalität zu prüfen, braucht es nur eine kleine Methode:

private boolean isPandigitalIdentity( int a, int b, int c ) {
 
   int sum = ( ( int ) Math.pow( 2, 10 ) ) - 1;
 
   for( int x : new int[]{ a, b, c } ) {
      while( x > 0 ) {
         int mod = x % 10;
         if( ( sum & powers2[ mod ] ) != 0 ) {
            sum -= powers2[ mod ];
         } else {
            return false;
         }
         x /= 10;
      }
   }
 
   if( sum != 1 )
      return false;
 
   return true;
}

Den vollständigen Quellcode der Klasse für die Lösung des Problems 32 kann man sich hier anschauen!

<< Problem 31 Übersicht Problem 33 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: