Today’s boredom lead me to solving another programming praxies problem:

Search every power of two below 2

^{10000}and return the index of the first power of two in which a target string appears. For instance, if the target is 42, the correct answer is 19 because 2^{19}= 524288, in which the target 42 appears as the third and fourth digits, and no smaller power of two contains the string 42.

The naive solution is simple: keep doubling a number (starting at 1) until you find a sequence that matches the target. Of course once you get 2^64 storing the number as a primitive type will not suffice, where you would need to come up with a solution to store larger numbers.

I improved on the naive approach by caching the number sequences for each exponent. For the cache I used a type of suffix tree:

private class SuffixTreeNode { public short MinExponent; public SuffixTreeNode[] Children; }

Unlike your traditional suffix tree, this one does not compress string sequences. It’s really just a trie, where the number in each sequence is stored implicitly as the index in Children (i.e. these arrays are of length 10). However the data structure is populated and access like a suffix tree: where each suffix of a number sequence is inserted into the tree. Each node in the tree is annotated with the smallest exponent that the sequence can be found in.

Here is the full code:

public static class DigitStringPowerTwoSearch { private static SuffixTreeNode suffixRoot; private static short currentExponent; private static List<int> currentDigits; static DigitStringPowerTwoSearch () { FlushCache (); } internal static void FlushCache() { // Exposed as internal really for unit tests only currentExponent = 0; currentDigits = new List<int> { 1 }; suffixRoot = new SuffixTreeNode (); AddDigitsToTree (currentDigits, 0, 0); } public static int FindMinBaseTwoExponent(ulong target) { var targetDigits = ToDigitArray(target); while (currentExponent <= 10000) { short exponent = FindMinExponentInTree(targetDigits); if (exponent >= 0) return exponent; AddNextExponentToTree(); } throw new ArgumentOutOfRangeException ("target", "target's digits do not exist in a base two number with exponent " + "less or equal to 10,000"); } private static void AddNextExponentToTree() { DoubleDigits (currentDigits); currentExponent++; for (int i = 0; i < currentDigits.Count; i++) { AddDigitsToTree (currentDigits, i, currentExponent); } } private static void AddDigitsToTree(IList<int> digits, int startIndex, short exponent) { SuffixTreeNode current = suffixRoot; for (int i = startIndex; i < digits.Count; i++) { int digit = digits [i]; if (current.Children == null) { current.Children = new SuffixTreeNode[10]; } if (current.Children [digit] == null) { var newNode = new SuffixTreeNode { MinExponent = exponent }; current.Children [digit] = newNode; current = newNode; } else { current = current.Children [digit]; // Here we assume exponent is always the largest exponent, // so no need to check/update current.MinExponent } } } private static short FindMinExponentInTree(int[] targetDigits) { SuffixTreeNode current = suffixRoot; foreach(var digit in targetDigits) { if (current == null || current.Children == null) return -1; current = current.Children[digit]; } if (current == null) return -1; return current.MinExponent; } private static int[] ToDigitArray(ulong n) { if (n == 0) return new int[] { 0 }; var digits = new List<int>(); for (; n != 0; n /= 10) digits.Add((int)(n % 10)); var arr = digits.ToArray(); Array.Reverse(arr); return arr; } private static void DoubleDigits(List<int> digits) { bool carry = false; for (int i = digits.Count - 1; i >= 0; i--) { int d = digits [i] * 2; if (carry) d++; if (d >= 10) { d -= 10; carry = true; } else { carry = false; } digits [i] = d; } if (carry) digits.Insert (0, 1); } private class SuffixTreeNode { public short MinExponent; public SuffixTreeNode[] Children; } }

When the function is invoked, if a sequence of numbers have been seen before, then we get O(N) performance (where N = amount of digits in target). Effectively the cache becomes a hash-trie.