Finding Digit Strings In Powers Of Two

September 24, 2013

[ I told you in a previous exercise that I was having internet connectivity issues at home. It took three weeks, but a repairman from the local telephone company finally found that, during repairs on the soffit underneath my roof overhang, the roofer nailed through a board with a nail that was too long, so it penetrated the board and the telephone cable that was nailed to the other side of the board. As the temperature and humidity changed during the day, sometimes the nail made contact with two ends of the same conductor, and everything worked properly, but sometimes the nail made contact with two different conductors, causing a short circuit and preventing the telephone from working. At the same time, my wifi router developed some kind of internal problem, also intermittent. I have now replaced both the wire and the router and everything seems to be working. The problems were hard to solve because both of them were intermittent. ]

Today’s problem comes from one or another of the competitive programming sites, I’m not sure which:

Search every power of two below 210000 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 219 = 524288, in which the target 42 appears as the third and fourth digits, and no smaller power of two contains the string 42.

Your task is to write the search program described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

9 Responses to “Finding Digit Strings In Powers Of Two”

  1. Paul said

    Rather easy in Python. The functions returns -1 of no index is found.

    POW2 = [2 **i for i in xrange(10000)]
    def find_pow2(n):
        target = str(n)
        for i, p in enumerate(POW2):
            if target in str(p):
                return i
        return -1
    
  2. Graham said

    I rather like Haskell’s Maybe.

    import Data.List (isInfixOf)
    
    powersOf2 :: [Integer]
    powersOf2 = map (2^) [0..]
    
    findPow2 :: String -> Maybe Int
    findPow2 s = aux 0
        where
            aux i | i > 10000                           = Nothing
                  | isInfixOf s $ show (powersOf2 !! i) = Just i
                  | otherwise                           = aux $ i + 1
    
  3. programmingpraxis said

    Graham: The corresponding idiom in Scheme is to return an empty list ‘() for Nothing and a non-empty list containing the value ‘(x) for Just. Those two return values are easy to distinguish by the null? and pair? predicates, and since both are lists there is no issue of type mis-match as there would be if you returned say an integer for the value x or the boolean #f for Nothing.

    Paul and Graham: I think for both of you it would be quicker to build your list of powers of two by repeatedly multiplying by two, as the suggested solution does, rather than exponentiating at each step.

  4. Paul said

    Indeed it is slower to use 2**i for each step. Here a version where the string representations for all powers arecalculated first (costs a little time).

    POW2 = []
    x = 1
    for i in xrange(10000):
        POW2.append(str(x))
        x *= 2
    
    def find_pow2(n):
        target = str(n)
        for i, p in enumerate(POW2):
            if target in p:
                return i
        return -1
    
  5. Graham said

    Fair enough!

    import Data.List (isInfixOf)
    
    powersOf2 :: [Integer]
    powersOf2 = 1 : map (2*) powersOf2
    
    findPow2 :: String -> Maybe Int
    findPow2 s = aux 0
        where
            aux i | i > 1000                            = Nothing
                  | isInfixOf s $ show (powersOf2 !! i) = Just i
                  | otherwise                           = aux $ i + 1
    

    I like the Scheme idiom and the Python version of returning -1 (or even throwing an exception,
    if the setting is right). I’m just recently somewhat enamored with Haskell’s types, though; they
    make the meaning of the code clear to me in a way that these idioms don’t, I guess.

  6. Prmk said

    //Using Java

    Double[] pow = new Double[1000];
    private void calculatePOW()
    {
    for(int i=0;i<1000;i++)
    pow[i] = Math.pow(2,i);
    }

    public int searchinPOW(int x)
    {
    int index = -1;

    for(int i=0;i<pow.length;i++)
    {
    double power = pow[i];
    if(String.valueOf(power).contains(String.valueOf(x)))
    {
    index = i;
    break;
    }
    }

    return index;
    }

  7. Prmk said

    Forgive my formatting !!

  8. In Racket:

    #lang racket
    
    (require srfi/13)
    
    (define (in-unfold f e)
      (letrec ([ps (stream-cons e (stream-map f ps))])
        ps))
    
    (define (find-power s)
      (for/first ([n (in-unfold (curry * 2) 1)]
                  [i (in-range 0 10000)]
                  #:when (string-contains (number->string n) s))
        i))
    
    ;; > (find-power "42")
    ;; 19
    ;; > (find-power "42679493")
    ;; #f
    
  9. brooknovak said

    Here is a C# solution with caching.

    I used a suffix trie to store the number sequences (without the compression the your usual suffix trie has).
    The numbers are stored implicitly as indexes in the children.
    I also annotated the minimum base-two exponent that can reach each node in the suffix tree.
    So if a digit sequence has been seen before, its O(n) performance (n = amount of digits).

    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;
    	}
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 612 other followers

%d bloggers like this: