# 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) {
else tree->l = createValueNodes(s);
}
else if (tree->v < *s) {
else tree->r = createValueNodes(s);
}
else if (tree->v == *s) {
if (++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;
}

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

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

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

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

return 0;
}```

### Python

```tree = [False, {}]

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) :
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.