Table of Contents
Two Two – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Two Two HackerRank Solution
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;
struct node
{
int e;
struct node *path[10];
};
int prodf[400],prodlen;
char bstr[123456];
struct node *posStack[300];
int stackSize=0;
struct node* addEdge(struct node *start, int edge)
{
if (start->path[edge]==NULL)
{
struct node *tempNode = new node;
tempNode->e=0;
for(int i=0;i<10;++i)
tempNode->path[i]=NULL;
start->path[edge]=tempNode;
}
return (start->path[edge]);
}
void markEnd(struct node *vnode)
{
vnode->e=1;
}
int main()
{
clock_t t_start =clock();
prodlen=1;
prodf[0]=1;
struct node *automaton = new struct node;
automaton->e=0;
for(int i=0;i<10;++i)
automaton->path[i]=NULL;
struct node *ppos=automaton;
ppos=addEdge(ppos,1);
markEnd(ppos);
for(int n=1;n<=800;++n)
{
int rem=0;
for(int i=0;i<prodlen;++i)
{
rem=(2*prodf[i]+rem);
prodf[i]=rem%10;
rem/=10;
}
if(rem!=0)
prodf[prodlen++]=rem;
ppos=automaton;
for(int i=prodlen-1;i>=0;--i)
{
ppos = addEdge(ppos,prodf[i]);
}
markEnd(ppos);
}
clock_t t_end=clock();
// cout<<(t_end+0.0-t_start)/CLOCKS_PER_SEC<<endl;
int T,k;
cin>>T;
while(T--)
{
long long ans=0;
stackSize=0;
scanf("%s",bstr);
for(int i=0,j;bstr[i]!='\0';++i)
{
k=bstr[i]-'0';
for(j=0;j<stackSize;)
{
if(posStack[j]->path[k]!=NULL)
{
posStack[j]=posStack[j]->path[k];
if(posStack[j]->e==1)
ans++;
++j;
}
else
posStack[j]=posStack[--stackSize];
}
if(automaton->path[k]!=NULL)
{
posStack[stackSize]=automaton->path[k];
if(posStack[stackSize]->e==1)
ans++;
++stackSize;
}
}
cout<<ans<<endl;
}
return 0;
}
Java Two Two HackerRank Solution
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;
struct node
{
int e;
struct node *path[10];
};
int prodf[400],prodlen;
char bstr[123456];
struct node *posStack[300];
int stackSize=0;
struct node* addEdge(struct node *start, int edge)
{
if (start->path[edge]==NULL)
{
struct node *tempNode = new node;
tempNode->e=0;
for(int i=0;i<10;++i)
tempNode->path[i]=NULL;
start->path[edge]=tempNode;
}
return (start->path[edge]);
}
void markEnd(struct node *vnode)
{
vnode->e=1;
}
int main()
{
clock_t t_start =clock();
prodlen=1;
prodf[0]=1;
struct node *automaton = new struct node;
automaton->e=0;
for(int i=0;i<10;++i)
automaton->path[i]=NULL;
struct node *ppos=automaton;
ppos=addEdge(ppos,1);
markEnd(ppos);
for(int n=1;n<=800;++n)
{
int rem=0;
for(int i=0;i<prodlen;++i)
{
rem=(2*prodf[i]+rem);
prodf[i]=rem%10;
rem/=10;
}
if(rem!=0)
prodf[prodlen++]=rem;
ppos=automaton;
for(int i=prodlen-1;i>=0;--i)
{
ppos = addEdge(ppos,prodf[i]);
}
markEnd(ppos);
}
clock_t t_end=clock();
// cout<<(t_end+0.0-t_start)/CLOCKS_PER_SEC<<endl;
int T,k;
cin>>T;
while(T--)
{
long long ans=0;
stackSize=0;
scanf("%s",bstr);
for(int i=0,j;bstr[i]!='\0';++i)
{
k=bstr[i]-'0';
for(j=0;j<stackSize;)
{
if(posStack[j]->path[k]!=NULL)
{
posStack[j]=posStack[j]->path[k];
if(posStack[j]->e==1)
ans++;
++j;
}
else
posStack[j]=posStack[--stackSize];
}
if(automaton->path[k]!=NULL)
{
posStack[stackSize]=automaton->path[k];
if(posStack[stackSize]->e==1)
ans++;
++stackSize;
}
}
cout<<ans<<endl;
}
return 0;
}
Python 3 Two Two HackerRank Solution
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])
Python 2 Two Two HackerRank Solution
import sys
MAX_EXP = 800
def main():
two_power_trie = make_two_power_trie()
for dig_str in testcases():
digs = [ord(c) - ord('0') for c in dig_str]
print count_matches(digs, two_power_trie)
def testcases(cin = sys.stdin):
t = int(cin.next())
for _ in xrange(t):
yield cin.next().strip()
def make_two_power_trie():
trie = [None] * 11
val = 1
for _ in xrange(MAX_EXP+1):
add_to_trie(trie, str(val))
val *= 2
return trie
def add_to_trie(trie, s, pos = 0):
if pos < len(s):
k = ord(s[pos]) - ord('0')
if trie[k] is None:
trie[k] = [None] * 11
add_to_trie(trie[k], s, pos+1)
else:
trie[10] = True
def count_matches(digits, trie):
ans = 0
for i in xrange(len(digits)):
cur = trie
for j in xrange(i, len(digits)):
cur = cur[digits[j]]
if cur is None: break
if cur[10]: ans += 1
return ans
if __name__ == "__main__": sys.exit(main())
C Two Two HackerRank Solution
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int read_int() {
int ret;
scanf("%d", &ret);
return ret;
}
/* caller should free the memory */
static int *read_int_array(int n) {
int *ret = malloc(n * sizeof(int));
for (int i = 0; i < n; ++i) {
scanf("%d", ret + i);
}
return ret;
}
static int intcomp(const void *v1, const void *v2) {
return *(const int *)v1 - *(const int *)v2;
}
#define BASE 801
static char powers[BASE][250];
static int power_nums[801];
static void build_powers() {
powers[0][0] = '1';
powers[0][1] = '\0';
power_nums[0] = 1;
for (int i = 1; i <= 800; ++i) {
int previous = power_nums[i - 1];
char *ppower = powers[i - 1];
int start_pos = previous;
if (ppower[0] >= '5') {
start_pos ++;
}
power_nums[i] = start_pos;
char *current = powers[i];
current[start_pos] = '\0';
int rem = 0;
for (int j = previous - 1; j >= 0; --j) {
int val = (ppower[j] - '0') * 2 + rem;
rem = val / 10;
current[start_pos - 1] = '0' + (val % 10);
start_pos --;
}
if (rem != 0) {
/* assert(start_pos == 1); */
current[0] = '0' + rem;
}
}
}
struct node {
struct node *childs;
char child_count;
char c;
/* -3 not initialized
* -2 invalid
* -1 root
* 0 normal
* 1 end!
*/
char end;
};
static void init_node(struct node *n, char c, char end) {
/* n->childs = malloc(10 * sizeof(struct node)); */
/* n->child_count = 10; */
/* for (int i = 0; i < 10; ++i) { */
/* n->c = '0' + i; */
/* n->childs[i].end = -3; */
/* } */
n->c = c;
n->end = end;
}
static struct node *build_node() {
struct node * root = malloc(sizeof(struct node));
init_node(root, 0, -1);
for (int i = 0; i < BASE; ++i) {
struct node *n = root;
for (const char *iter = powers[i]; *iter; iter++) {
/* struct node *child = n[*iter - '0']; */
if (!n->childs) {
/* n = malloc(sizeof(struct node)); */
/* init_node(child, ) */
n->childs = malloc(10 * sizeof(struct node));
n->child_count = 10;
for (int i = 0; i < 10; ++i) {
n->childs[i].c = '0' + i;
/* n->childs[i].end = -3; */
}
}
n = n->childs + (*iter - '0');
}
n->end = 1;
}
return root;
}
static long long int count_appearance(const char *haystack, const char *needle) {
long long int result = 0;
while (1) {
if ((haystack = strstr(haystack, needle))) {
result ++;
haystack++;
} else {
return result;
}
}
}
static long long int solve(const char *buffer, struct node *root) {
/* int len = strlen(buffer); */
/* long long int result = 0; */
/* for (int i = 0; i < BASE && power_nums[i] <= len; ++i) { */
/* result += count_appearance(buffer, powers[i]); */
/* /\* printf("result: %lld\n", result); *\/ */
/* } */
/* return result; */
long long result = 0;
for (const char *iter = buffer; *iter; ++iter) {
/* printf("ITER: %c\n", *iter); */
struct node *n = root;
for (const char *iter2 = iter; *iter2; ++iter2) {
/* printf("ITER2: %c end %d\n", *iter2, n->end); */
if (!n->childs) {
/* previous is the end */
break;
} else {
n = &n->childs[*iter2 - '0'];
if (n->end) {
result++;
}
}
}
}
return result;
}
int main(int argc, char *argv[]) {
build_powers();
struct node *root = build_node();
/* struct node *n = &(root->childs[1]); */
/* printf("%d %c %d ccount: %d\n", n->c, n->c, n->end, n->child_count); */
int t = read_int();
char buffer[100001];
for (int i = 0; i < t; ++i) {
scanf(" %s", buffer);
printf("%lld\n", solve(buffer, root));
}
return 0;
}
