Two Two – HackerRank Solution

In this post, we will solve Two Two HackerRank Solution. This problem (Two Two) is a part of HackerRank Problem Solving series.

Solution – Two Two – HackerRank Solution

C++

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

class Node {
  public:
    char v;
    Node* l;
    Node* r;
    Node* m;
    bool leaf;
  Node(char val) : v(val), leaf(false), 
    l(NULL), r(NULL), m(NULL) {}
};


char buf1[800];
char buf2[800];
Node* power_tree = NULL;

void mul2(char* src, char* dst, int &len) {
    int offset = (src[0] > '4') ? 1 : 0;
    char v, carry=0;
    dst[len] = 0;
    for (int i=len-1; i>=0; i--) {
        v = ((src[i] - '0') * 2)  + carry;
        carry = (v>9) ? 1 : 0;
        dst[i+offset] = (v%10) + '0';
    }
    if (offset) {
        dst[0] = '1';
        len++;
    }
}

Node* createValueNodes(char* s) {
    Node *res = NULL;
    Node *cur = NULL;
    while (*s) {
        Node* n = new Node(*s);
        if (res==NULL) {
            cur = res = n;
        } else {
            cur->m = n;
            cur = n;
        }
        s++;
    }
    cur->leaf = true;
    return res;
}

Node* addValue(Node* tree, char* s) {
    if (tree==NULL) return createValueNodes(s);
    if (tree->v > *s) {
        if (tree->l) addValue(tree->l, s);
        else tree->l = createValueNodes(s);
    }
    else if (tree->v < *s) {
        if (tree->r) addValue(tree->r, s);
        else tree->r = createValueNodes(s);
    }
    else if (tree->v == *s) {
        if (++s) {
            if (tree->m) addValue(tree->m, s);
            else tree->m = createValueNodes(s);
        } else {
            tree->leaf = true;
        }
    }
    return tree;
}

int find(Node* tree, const char* s) {
    int res = 0;
    while (tree && *s) {
        if (tree->v > *s) tree = tree->l;
        else if (tree->v < *s) tree = tree->r;
        else if (tree->v == *s) {
            if (tree->leaf) res++;
            tree = tree->m;
            s++;
        }
    }
    return res;
}

void load_tree() {
    int len = 1;
    buf1[0] = '1';
    buf1[1] = 0;
    power_tree = addValue(power_tree, buf1);
    for (int i=0; i<400; i++) {
        mul2(buf1, buf2, len);
        power_tree = addValue(power_tree, buf2);
        mul2(buf2, buf1, len);
        power_tree = addValue(power_tree, buf1);
    }
}

int count_powers(string s) {
    int total = 0;
    const char* str = s.c_str();
    for (int i=0; i<s.length(); i++) {
        total += find(power_tree, str+i);
    }
    return total;
}

int main() {
    string s;
    int t;
    cin >> t;

    load_tree();
    for (int i=0; i<t; i++) {
        cin >> s;
        cout << count_powers(s) << endl;
    }

    return 0;
}

Python

tree = [False, {}]

def add(word) :
    current = tree
    for c in word :
        try :
            current = current[1][c]
        except KeyError :
            current[1][c] = [False, {}]
            current = current[1][c]
    current[0] = True
    
def count(word) :
    count = 0
    for start in range(len(word)) :
        current, index = tree, start
        while True :
            if current[0] :
                count += 1
            try :
                current = current[1][word[index]]
                index += 1
            except (KeyError, IndexError) :
                break
    return count
    
v = 1
for x in range(801) :
    add(str(v)[::-1])
    v <<= 1

Done = {}    
T = int(input())
for t in range(T) :
    A = input()
    if not A in Done :
        Done[A] = count(A[::-1])
    print(Done[A])

Java

import java.util.Scanner;
import java.math.BigInteger;
public class TwoTwo {
    static class Trie {
        boolean end;
        Trie[]children;
        Trie() {
            end = false;
            children = new Trie[10];
        }
        void insert(String val) {
            if(val.length() == 0) {
                end = true;
                return;
            }
            //int index = val.charAt(0) - '0';
            int index = val.charAt(val.length() - 1) - '0';
            if(children[index] == null)
                children[index] = new Trie();
            //children[index].insert(val.substring(1));
            children[index].insert(val.substring(0, val.length() - 1));
        }
    }
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        Trie trie = new Trie();
        BigInteger x = BigInteger.ONE;
        trie.insert(x.toString());
        for(int i = 0; i < 800; ++i) {
            x = x.shiftLeft(1);
            trie.insert(x.toString());
        }
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        in.nextLine();
        while(T-- > 0) {
            String s = in.nextLine();
            long count = 0;
            for(int i = 0; i < s.length(); ++i) {
                Trie node = trie.children[s.charAt(i) - '0'];
                if(node == null) continue;
                if(node.end) ++count;
                for(int j = 1; j < 243; ++j) {
                    if(i - j < 0) break;
                    node = node.children[s.charAt(i - j) - '0'];
                    if(node == null) break;
                    if(node.end) ++count;
                }
            }
            System.out.println(count);
        }
        //System.out.println("time " + (System.currentTimeMillis() - start));
    }
}

Note: This problem (Two Two) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.