2
\$\begingroup\$

Overview

I was challenged recently to write some code that could find the smallest integer that when multiplied and divided by 2 or 3, retained all of its digits and gained no extras. For example:

  • With 2
    • 285714
      1. When multiplied: 571428.
      2. When divided: 142857.
  • With 3
    • 31046895
      1. When multiplied: 93140685.
      2. When divided: 10348965.

Code

You'll need the following using statements:

using System;
using System.Collections.Generic;
using static System.Console;

The Main method contents:

int variant = 2;
for (int i = 0; i < int.MaxValue; i++)
    if (ProductAndFactor(i, variant)) {
        WriteLine(i);
        break;
    }

WriteLine("Done");
ReadKey();

The backbone code:

static bool ProductAndFactor(int i, int v) {
    Dictionary<char, int> oChars = GetValueChars(i);
    Dictionary<char, int> dChars = GetValueChars(i / v);
    Dictionary<char, int> mChars = GetValueChars(i * v);

    if ($"{i}".Length != $"{i / v}".Length ||
        $"{i}".Length != $"{i * v}".Length)
        return false;

    foreach (char c in oChars.Keys) {
        if (!dChars.ContainsKey(c)) return false;
        else if (dChars[c] != oChars[c]) return false;
        else if (!pChars.ContainsKey(c)) return false;
        else if (pChars[c] != oChars[c]) return false;
    }

    WriteLine($"{i} * {v} = {i * v}\n{i} / {v} = {i / v}");
    return true;
}
static Dictionary<char, int> GetValueChars(int i) {
    Dictionary<char, int> chars = new Dictionary<char, int>();
    foreach (char c in i.ToString()) {
        if (chars.ContainsKey(c)
            chars[c]++;
        else
            chars.Add(c, 1);
    }
    return chars;
}

My Question

Is there a more simplistic way to accomplish this? I can't help but feel like there is and that using Dictionary<char, int> is probably an inefficient option in this task unless there is a smart way to reuse it.

  • Is there a more simplistic way to accomplish this?
  • Are there more efficient data types to utilize in this use-case?
    • What are they?
    • Why are they more efficient?
  • Is there a smarter way to reach the answer faster?

Also, if I used the wrong tags, or more tags are needed, please edit and add them.


Benchmarks

For v = 2 the discovery time was 4 seconds. For v = 3 the discovery time was 112 seconds.

\$\endgroup\$
  • \$\begingroup\$ I'm not happy with the performance tag. Usually when I see it I expect to find some benchmarks and measurements etc. in the question because without them it's very difficult to tell whether a perticualar solution is performing better or worse. So if you have such benchmarks then please add them especially that you are searching for the number in the entire int range (int.MaxValue). \$\endgroup\$ – t3chb0t Oct 15 '18 at 16:44
2
\$\begingroup\$

The trick is to search for j = i / v instead of j = i:

that means to search for i and i * v and i * v * v:

static bool ProductAndFactor(int i, int v)
{
  if ($"{i}".Length != $"{i * v}".Length ||
      $"{i}".Length != $"{i * v * v}".Length)
    return false;

  Dictionary<char, int> oChars = GetValueChars(i);
  Dictionary<char, int> dChars = GetValueChars(i * v);
  Dictionary<char, int> mChars = GetValueChars(i * v * v);

  foreach (char c in oChars.Keys)
  {
    if (!dChars.ContainsKey(c)) return false;
    else if (dChars[c] != oChars[c]) return false;
    else if (!mChars.ContainsKey(c)) return false;
    else if (mChars[c] != oChars[c]) return false;
  }

  return true;
}

or in other words you search for the smallest value to find rather than the middle value.

Notice that I've moved the length tests above the Dictionary stuff, because there is no need for that if the lengths differs.


    int variant = 3;
    for (int i = 1; i < int.MaxValue; i++)
    {
      if (ProductAndFactor(i, variant))
      {
        Console.WriteLine($"{i} => {i * variant} => {i * variant * variant}");
        break;
      }
    }

Another version could be:

static bool ProductAndFactor(int i, int v)
{
  int iv = i * v;
  int ivv = i * v * v;

  int[] ai = new int[10];
  int[] aiv = new int[10];
  int[] aivv = new int[10];

  while (i > 0)
  {
    ai[i % 10]++;
    aiv[iv % 10]++;
    aivv[ivv % 10]++;

    i /= 10;
    iv /= 10;
    ivv /= 10;
  }

  for (int j = 0; j < 10; j++)
  {
    if (ai[j] != aiv[j] || ai[j] != aivv[j])
      return false;
  }

  return iv == 0 && ivv == 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.