Fastest way to check if a number is a vampire number?

Question

A vampire number is defined here https://en.wikipedia.org/wiki/Vampire_number. A number V is a vampire number if:

• It can be expressed as X*Y such that X and Y have N/2 digits each where N is the number of digits in V
• Both X & Y should not have trailing zeros
• X & Y together should have the same digits as V

I came up with a solution,

strV = sort(toString(V))
for factor <- pow(10, N/2) to sqrt(V)
    if factor divides V
        X <- factor
        Y <- V/factor
        if X and Y have trailing zeros
           continue
        checkStr = sort(toString(X) + toString(Y))
        if checkStr equals strV return true

Another possible solution is to permute the string represented by V and split it into half and check if its a vampire number. Which one is the best way to do so?

Inly

What is your definition of 'best' here? Less code? Faster? Easier to comprehend (often an underestimated factor)? – Claymore

You could give this a try on the math stack exchange – Bevis

@RadLexus Faster as in less asymptotic complexity/runtime – Inly

In that case: the need for a conversion to string and sorting it could be replaced with a one-dimensional array, holding a count for each digit (perhaps even a simple bit mask is enough). That removes the sorting part, which is always time complex. Can't comment on the division and the limits, though. – Claymore

Did any of the answers suit your needs? Could you leave a comment or accept an answer? – Efficient

Answer 1

In pseudocode:

if digitcount is odd return false
if digitcount is 2 return false
for A = each permutation of length digitcount/2 selected from all the digits,
  for B = each permutation of the remaining digits,
    if either A or B starts with a zero, continue
    if both A and B end in a zero, continue
    if A*B == the number, return true

There are a number of optimizations that could still be performed here, mostly in terms of ensuring that each possible pair of factors is tried only once. In other words, how to best check for repeating digits when selecting permutations?

But that's the gist of the algorithm I would use.

P.S.: You're not looking for primes, so why use a primality test? You just care about whether these are vampire numbers; there are only a very few possible factors. No need to check all the numbers up to sqrt(number).

Marceline

Agreed with the first part, but you don't need the 2nd loop. Test if V%A is 0 and if V/A=B has all the remaining digits and no rules are violated. That with not looking at the same numbers twice is indeed tricky, one way to solve it is to use a hash map. – Darelldarelle

@Darelldarelle avoiding redundant tests is going to add complexity, likely eliminating the savings from not testing a number twice. I wouldn't worry about it. – Arellano

@MarkRansom, actually I think maraca is right. Instead of testing individual values for "B" and multiplying, just testing if V%A == 0 is almost certainly faster. – Marceline

@Marceline I agree. I was talking about the second part of the statement, using a hashmap to avoid duplicate testing. – Arellano

Answer 2

The algorithm I propose here will not go through all permutations of digits. It will eliminate possibilities as fast as possible so that only a fraction of permutations will actually be tested.

Algorithm explained by example

Here is how it works based on example number 125460. If you are fine with reading the code directly, then you can skip this (long) part:

At first the two fangs (i.e. vampire factors) are obviously not known, and the problem can be represented as follows:

       ?**
   X   ?**
   -------
   =125460

For the left most digit of the first factor (marked with ?) we could choose any of the digits 0,1,2,5,4, or 6. But on closer analysis 0 would not be a viable possibility, as the product would never reach more than a 5-digit number. So it would be a waste of time to go through all permutations of digits that start with a zero.

For the left most digit of the second factor (also marked with ?), the same is true. However, when looking at the combinations, we can again filter out some pairs that cannot contribute to reaching the target product. For instance, this combination should be discarded:

       1**
   X   2**
   -------
   =125460

The greatest number that can be achieved with these digits is 199x299 = 59501 (ignoring the fact that we don't even have a 9), which is not even half of the desired number. So we should reject the combination (1, 2). For the same reason, the pair (1, 5) can be discarded for taking these positions. Similarly, the pairs (4, 5), (4, 6), and (5, 6) can be rejected as well, because they yield a too large product (>= 200000). I will call this kind of a test -- where it is determined whether the target number is within reach for a certain chosen digit pair, the "range test".

At this stage there is no difference between the first and the second fang, so we should also not have to investigate pairs where the second digit is smaller than the first, because they mirror a pair that would already have been investigated (or rejected).

So of all the possible pairs that could take up this first position (there are 30 possibilities to take 2 digits from a set of 6 digits), only the following 4 need to be investigated:

(1, 6), (2, 4), (2, 5), (2, 6)

In a more elaborate notation this means we are limiting the search to these number patterns:

       1**       2**       2**       2**
   X   6**   X   4**   X   5**   X   6**
   -------   -------   -------   -------
   =125460   =125460   =125460   =125460

       A         B         C         D

It is clear that this reduction of possibilities before even looking at the other positions greatly reduces the search tree.

The algorithm will take each of these 4 possibilities in order, and for each will check the possibilities for the next digit position. So first configuration A is analysed:

       1?*
   X   6?*
   -------
   =125460

The pairs that are available for the ?-marked positions are these 12:

(0, 2), (0, 4), (0, 5)
(2, 0), (2, 4), (2, 5)
(4, 0), (4, 2), (4, 5)
(5, 0), (5, 2), (5, 4)

Again, we can eliminate pairs by applying the range test. Let's take for instance the pair (5, 4). This would mean we had factors 15* and 64* (where * is an unknown digit at this point). The product of these two will be maximised with 159 * 649, i.e. 103191 (again ignoring the fact we do not even have a 9 available): this is too low for reaching the target, so this pair can be ignored. By further applying the range test, all these 12 pairs can be discarded, and so the search within configuration A stops here: there is no solution there.

Then the algorithm moves to configuration B:

       2?*
   X   4?*
   -------
   =125460

Again, the range test is applied to the possible pairs for the second position, and again it turns out none of these pairs passes the test: for instance (5, 6) can never represent a greater product than 259 * 469 = 121471, which is (only just) too small.

Then the algorithm moves to option C:

       2?*
   X   5?*
   -------
   =125460

Of all 12 possible pairs, only the following survive the range test: (4, 0), (4, 1), (6, 0), (6, 1). So now we have the following second-level configurations:

       24*       24*       26*       26*
   X   50*   X   51*   X   50*   X   51*
   -------   -------   -------   -------
   =125460   =125460   =125460   =125460

       Ca        Cb        Cc        Cd

In configuration Ca, there is no pair that passes the range test.

In configuration Cb, the pair (6, 0) passes, and leads to a solution:

       246
   X   510
   -------
   =125460

At this point the algorithm stops searching. The outcome is clear. In total the number of configurations looked at is very small compared to a brute force permutation checking algorithm. Here is a visualisation of the search tree:

 *-+-- (1, 6)
   |
   +-- (2, 4)
   |
   +-- (2, 5) -+-- (4, 0)
   |           |
   |           +-- (4, 1) ---- (6, 0) = success: 246 * 510
   /           /
   |           +-- (6, 0)
   |           |
   |           +-- (6, 1)
   |
   +-- (2, 6) ---- (0, 1) ---- (4, 5) = success: 204 * 615

The variants below / are only for showing what else the algorithm would have done, if there had not been a solution found. But in this actual case, that part of the search tree was actually never followed.

I have no clear idea of the time complexity, but it seems to run quite well for larger numbers, showing that the elimination of digits at an early stage makes the width of the search tree quite narrow.

Here is a live JavaScript implementation, which also runs some test cases when it it is activated (and it has a few other optimisations -- see code comments).

/*
    Function: vampireFangs
    Arguments:
        vampire: number to factorise into two fangs, if possible.
    Return value:
        Array with two fangs if indeed the argument is a vampire number.
        Otherwise false (not a vampire number) or null (argument too large to 
        compute) 
*/
function vampireFangs(vampire) {
    /* Function recurse: for the recursive part of the algorithm.
       prevA, prevB: partial, potential fangs based on left-most digits of the given 
                     number
       counts: array of ten numbers representing the occurrence of still 
                     available digits
       divider: power of 100, is divided by 100 each next level in the search tree.
                Determines the number of right-most digits of the given number that 
                are ignored at first in the algorithm. They will be considered in 
                deeper levels of recursion.
    */
    function recurse(vampire, prevA, prevB, counts, divider) {
        if (divider < 1) { // end of recursion
            // Product of fangs must equal original number and fangs must not both 
            // end with a 0.
            return prevA * prevB === vampire && (prevA % 10 + prevB % 10 > 0)
                ? [prevA, prevB] // Solution found
                : false; // It's not a solution
        }
        // Get left-most digits (multiple of 2) of potential vampire number
        var v = Math.floor(vampire/divider);
        // Shift decimal digits of partial fangs to the left to make room for 
        // the next digits
        prevA *= 10;
        prevB *= 10;
        // Calculate the min/max A digit that can potentially contribute to a 
        // solution
        var minDigA = Math.floor(v / (prevB + 10)) - prevA;
        var maxDigA = prevB ? Math.floor((v + 1) / prevB) - prevA : 9;
        if (maxDigA > 9) maxDigA = 9;
        for (var digA = minDigA; digA <= maxDigA; digA++) {
            if (!counts[digA]) continue; // this digit is not available
            var fangA = prevA + digA;
            counts[digA]--;
            // Calculate the min/max B digit that can potentially contribute to 
            // a solution
            var minDigB = Math.floor(v / (fangA + 1)) - prevB;
            var maxDigB = fangA ? (v + 1) / fangA - prevB : 9;
            // Don't search mirrored A-B digits when both fangs are equal until now.
            if (prevA === prevB && digA > minDigB) minDigB = digA;
            if (maxDigB > 9) maxDigB = 9;
            for (var digB = minDigB; digB <= Math.min(maxDigB, 9); digB++) {
                if (!counts[digB]) continue; // this digit is not available
                var fangB = prevB + digB;
                counts[digB]--;
                // Recurse by considering the next two digits of the potential 
                // vampire number, for finding the next digits to append to 
                // both partial fangs.
                var result = recurse(vampire, fangA, fangB, counts, divider / 100);
                // When one solution is found: stop searching & exit search tree.
                if (result) return result; // solution found
                // Restore counts
                counts[digB]++;
            }
            counts[digA]++;
        }
    }


    // Validate argument
    if (typeof vampire !== 'number') return false;
    if (vampire < 0 || vampire % 1 !== 0) return false; // not positive and integer
    if (vampire > 9007199254740991) return null; // beyond JavaScript precision 
    var digits = vampire.toString(10).split('').map(Number);
    // A vampire number has an even number of digits
    if (!digits.length || digits.length % 2 > 0) return false;
    
    // Register per digit (0..9) the frequency of that digit in the argument
    var counts = [0,0,0,0,0,0,0,0,0,0];
    for (var i = 0; i < digits.length; i++) {
        counts[digits[i]]++;
    }
    
    return recurse(vampire, 0, 0, counts, Math.pow(10, digits.length - 2));
}

function Timer() {
    function now() { // try performance object, else use Date
        return performance ? performance.now() : new Date().getTime();
    }
    var start = now();
    this.spent = function () { return Math.round(now() - start); }
}

// I/O
var button = document.querySelector('button');
var input = document.querySelector('input');
var output = document.querySelector('pre');

button.onclick = function () {
    var str = input.value;
    // Convert to number
    var vampire = parseInt(str);
    
    // Measure performance
    var timer = new Timer();

    // Input must be valid number
    var result = vampire.toString(10) !== str ? null 
                 : vampireFangs(vampire);

    output.textContent = (result 
            ? 'Vampire number. Fangs are: ' + result.join(', ') 
            : result === null 
                    ? 'Input is not an integer or too large for JavaScript' 
                    : 'Not a vampire number')
       + '\nTime spent: ' + timer.spent() + 'ms';
}

// Tests (numbers taken from wiki page)

var tests = [
    // Negative test cases:
    [1, 999, 126000, 1023],
    // Positive test cases:
    [1260, 1395, 1435, 1530, 1827, 2187, 6880, 
    102510, 104260, 105210, 105264, 105750, 108135, 
    110758, 115672, 116725, 117067, 118440, 
    120600, 123354, 124483, 125248, 125433, 125460, 125500,
    13078260,
    16758243290880,
    24959017348650]
];
tests.forEach(function (vampires, shouldBeVampire) {
    vampires.forEach(function (vampire) {
        var isVampire = vampireFangs(vampire);
        if (!isVampire !== !shouldBeVampire) {
            output.textContent = 'Unexpected: vampireFangs(' 
                    + vampire + ') returns ' + JSON.stringify(isVampire);
            throw 'Test failed';
        }
    });
});
output.textContent = 'All tests passed.';

N: <input value="1047527295416280"><button>Vampire Check</button>
<pre></pre>

As JavaScript uses 64 bit floating point representation, the above snippet only accepts to numbers up to 2⁵³-1. Above that limit there would be loss of precision and consequently unreliable results.

As Python does not have such limitation, I also put a Python implementation on eval.in. That site has a limitation on execution times, so you'd have to run it elsewhere if that becomes an issue.

Efficient

that's a pity, the answers with much work are not really rewarded. – Trapezius

A nice answer. I always appreciate it when people invest energy in both finding an efficient solution and take time to explain it decently. +1. – Unharness

Wow, impressive! For the record, I think this is much better than my own (relatively naive) solution. :) – Marceline

Answer 3

Here are some suggestions:

1. First a simple improvement: if the number of digits is < 4 or odd return false (or if v is negative too).

2. You don't need to sort v, it is enough to count how many times each digit occurs O(n).

3. You don't have to check each number, only the combinations that are possible with the digits. This could be done by backtracking and significantly reduces the amount of numbers that have to be checked.

4. The final sort to check if all digits were used isn't needed either, just add up the used digits of both numbers and compare with the occurences in v.

Here is the code for a JS-like language with integers that never overflow, the V parameter is an integer string without leading 0s:

Edit: As it turns out the code is not only JS-like, but valid JS code and it had no problem to decide that 1047527295416280 is indeed a vampire number (jsfiddle).

var V, v, isVmp, digits, len;

function isVampire(numberString) {
  V = numberString;
  if (V.length < 4 || V.length % 2 == 1 )
    return false;
  v = parseInt(V);
  if (v < 0)
    return false;
  digits = countDigits(V);
  len = V.length / 2;
  isVmp = false;
  checkNumbers();
  return isVmp;
}

function countDigits(s) {
  var offset = "0".charCodeAt(0);
  var ret = [0,0,0,0,0,0,0,0,0,0];
  for (var i = 0; i < s.length; i++)
    ret[s.charCodeAt(i) - offset]++;
  return ret;
}

function checkNumbers(number, depth) {
  if (isVmp)
    return;
  if (typeof number == 'undefined') {
    for (var i = 1; i < 10; i++) {
      if (digits[i] > 0) {
        digits[i]--;
        checkNumbers(i, len - 1);
        digits[i]++;
      }
    }
  } else if (depth == 0) {
    if (v % number == 0) {
      var b = v / number;
      if (number % 10 != 0 || b % 10 != 0) {
        var d = countDigits('' + b);
        if (d[0] == digits[0] && d[1] == digits[1] && d[2] == digits[2] &&
            d[3] == digits[3] && d[4] == digits[4] && d[5] == digits[5] &&
            d[6] == digits[6] && d[7] == digits[7] && d[8] == digits[8] &&
            d[9] == digits[9])
          isVmp = true;
      }
    }
  } else {
    for (var i = 0; i < 10; i++) {
      if (digits[i] > 0) {
        digits[i]--;
        checkNumbers(number * 10 + i, depth - 1);
        digits[i]++;
      }
    }
  }
}

Darelldarelle