Multiple permutations
Published on Tuesday, August 9, 2011Woohoo! I've gotten through all Euler problems solved by more than 20,000 people — not an official milestone, but one that feels important nonetheless. The last of these, the tersely-worded problem 52, concerned multiples/permutations:
It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.
Find the smallest positive integer, x, such that 2_x_, 3_x_, 4_x_, 5_x_, and 6_x_, contain the same digits.
To me, the phrase “find the smallest positive integer that ____” cries out for a brute force solution. There didn't seem to be anyway to preëmptively exclude certain values from being tested to see if they fit the problem requirements, so I focused on optimizing my testing algorithm. I borrowed a few lines of code from my solutions to problems 32 and 38 that check to see if one number is a permutation of another. If you take a number, convert it to a string, convert that string to a character array, and then sort that array, you will end up with the same array as you would performing the same sequence of operations on a permutation of the original number. Comparing the sorted character arrays derived from two numbers will tell you if they are permutations of each other.
Rather than checking each value x
against 2x
, 3x
, 4x
, 5x
, and 6x
, I checked it first against 2x
, then against 3x
, then against 4x
, and so on, moving to the next value x
when nx
didn't yield a permutation of x
.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Problem052
{
class Program
{
static void Main(string[] args)
{
int permutableMultiples = 0;
bool multipleFound = false;
for (int i = 1; !multipleFound; i++)
{
string baseMultiple = i.ToString();
char[] baseChars = baseMultiple.ToArray();
Array.Sort(baseChars);
for (int j = 2; j < 7; j++)
{
char[] baseMultiplied = (i * j).ToString().ToArray();
Array.Sort(baseMultiplied);
if (!baseChars.SequenceEqual(baseMultiplied))
break;
if (j == 6)
{
permutableMultiples = i;
multipleFound = true;
break;
}
}
}
Console.WriteLine(permutableMultiples);
}
}
}