Step by Step solution about How to resolve the algorithm Vampire number step by step in the C programming language

The provided C program determines if a given number is a vampiric number. A vampiric number is a number that can be represented as the product of two other numbers where the digits in the product match the digits in the original number.

Here's a breakdown of the code:

• Preprocessing Directives (Header Files):

  • The code includes several header files:
    • <stdio.h>: Input/Output operations.
    • <stdlib.h>: Standard library functions.
    • <stdint.h>: Integer types.
    • <math.h>: Mathematical functions.

• Type Definitions:

  • Two typedefs are defined:
    • xint: An unsigned 64-bit integer type.
    • ull: An alias for unsigned long long.

• Global Array:

  • An array tens is declared to store powers of 10 up to the 20th power.

• Helper Functions:

  • max(a, b) and min(a, b): Calculate the maximum and minimum of two xint values.
  • ndigits(x): Count the number of digits in an xint value.
  • dtally(x): Create a bitmask where each bit represents a digit in the xint value. For example, if x is 12345, the bitmask will be 0b11110010010101.

• Function fangs:

  • This function takes an xint value and an array of xint values f as parameters. It finds all factors of x that are vampiric numbers and stores them in the array f.
  • It does this by iterating through potential factors and checking if the product of the factors matches the original number and if the digit bitmasks of the factors match the digit bitmask of the original number.
  • It returns the number of factors found.

• Function show_fangs:

  • This function prints the given xint value and its vampiric factors.

• Main Function:

  • The main function starts by initializing the tens array and some example numbers to be tested.
  • It then enters a loop and iterates through numbers, checking for vampiric factors. For each vampiric number found, it prints the number and its factors.
  • It also checks the provided example numbers for vampiric factors and prints the results.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>

typedef uint64_t xint;
typedef unsigned long long ull;

xint tens[20];

inline xint max(xint a, xint b) { return a > b ? a : b; }
inline xint min(xint a, xint b) { return a < b ? a : b; }
inline int ndigits(xint x)
{
	int n = 0;
	while (x) n++, x /= 10;
	return n;
}

inline xint dtally(xint x)
{
	xint t = 0;
	while (x) t += 1<<((x%10) * 6), x /= 10;

	return t;
}

int fangs(xint x, xint *f)
{
	int n = 0;
	int nd = ndigits(x);
	if (nd & 1) return 0;
	nd /= 2;

	xint lo, hi;
	lo = max(tens[nd-1], (x + tens[nd] - 2)/ (tens[nd] - 1));
	hi = min(x / lo, sqrt(x));

	xint a, b, t = dtally(x);
	for (a = lo; a <= hi; a++) {
		b = x / a;
		if (a * b == x && ((a%10) || (b%10)) && t == dtally(a) + dtally(b))
			f[n++] = a;
	}

	return n;
}

void show_fangs(xint x, xint *f, xint cnt)
{
	printf("%llu", (ull)x);
	int i;
	for (i = 0; i < cnt; i++)
		printf(" = %llu x %llu", (ull)f[i], (ull)(x / f[i]));
	putchar('\n');
}

int main(void)
{
	int i, j, n;
	xint x, f[16], bigs[] = {16758243290880ULL, 24959017348650ULL, 14593825548650ULL, 0};

	tens[0] = 1;
	for (i = 1; i < 20; i++)
		tens[i] = tens[i-1] * 10;

	for (x = 1, n = 0; n < 25; x++) {
		if (!(j = fangs(x, f))) continue;
		printf("%2d: ", ++n);
		show_fangs(x, f, j);
	}

	putchar('\n');
	for (i = 0; bigs[i]; i++) {
		if ((j = fangs(bigs[i], f)))
			show_fangs(bigs[i], f, j);
		else
			printf("%llu is not vampiric\n", (ull)bigs[i]);
	}

	return 0;
}