HackerRank Two Two Problem Solution

In this post, we will solve HackerRank Two Two Problem Solution.

Prof. Twotwo as the name suggests is very fond powers of 2. Moreover he also has special affinity to number 800. He is known for carrying quirky experiments on powers of 2.

One day he played a game in his class. He brought some number plates on each of which a digit from 0 to 9 is written. He made students stand in a row and gave a number plate to each of the student. Now turn by turn, he called for some students who are standing continuously in the row say from index i to index j (i<=j) and asked them to find their strength.

The strength of the group of students from i to j is defined as:

strength(i , j)
{
    if a[i] = 0
        return 0; //If first child has value 0 in the group, strength of group is zero
    value = 0;
    for k from i to j
        value = value*10 + a[k]
    return value;
}

Prof called for all possible combinations of i and j and noted down the strength of each group. Now being interested in powers of 2, he wants to find out how many strengths are powers of two. Now its your responsibility to get the answer for prof.

Input Format

First line contains number of test cases T
Next T line contains the numbers of number plates the students were having when standing in the row in the form of a string A.

Constraints

1 ≤ T ≤ 100
1 ≤ len(A) ≤ 10⁵
0 ≤ A[i] ≤ 9

Output Format

Output the total number of strengths of the form 2^x such that 0 ≤ x ≤ 800.

Sample Input 0

Sample Output 0

Explanation 0

In following explanations group i-j is group of student from index i to index j (1-based indexing)

In first case only 2 is of form power of two. It is present seven times for groups 1-1,2-2,3-3,4-4,5-5,6-6,7-7
In second case 2,4 and 256 are of required form. 2 is strength of group 1-1 and 3-3, 4 is strength of group 2-2 and 256 is strength of group 3-5.
In third case 65536 is only number in required form. It is strength of group 1-5
In fourth case 2 and 32 are of forms power of 2. Group 1-2 has values 0,2 but its strength is 0, as first value is 0.
In fifth case, None of the group has strength of required form.

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

Two Two C++ Solution

// HackerRank Two Two solution
// mbr 20171215

#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int noState = -1;

int inline NewState(vector<pair<int,int>>& states, int& nextState)
{
	nextState += 10;
	for (int i = 0; i < 10; i++) states.push_back(make_pair(noState, 0));
	return nextState-10;
}

int main(void)
{
	int T;

	string p(256, '\0');	// conservative estimate for max length of pattern
	p[0] = '\1';
	int plen = 1;
	vector<pair<int,int>> state;
	int nextState = 0;
	int curState = NewState(state, nextState);
	for (int i = 0; i <= 800; i++) {
	  curState = 0;
	  int j = plen-1;
	  // traverse existing states
	  while (j > 0 && state[curState+p[j]].first >= 0) {
	    curState = state[curState+p[j]].first; j--;
	  }
	  // append new states
	  while (j > 0) {
	    int h = NewState(state, nextState);
	    state[curState+p[j]].first = h;
	    curState = h;
	    j--;
	  }
	  state[curState+p[0]].second++;	// increase match count
	  int carry = 0;
	  for (int j = 0; j < plen; j++) {
	    p[j] += p[j] + carry;
	    if (p[j] > '\x9') { p[j] -= '\xa'; carry = 1; }
	    else carry = 0;
	  }
	  if (carry > 0) p[plen++] = (char)carry;
	}
	cin >> T;
	while (--T >= 0) {
	  string s;
	  cin >> s;
	  int count = 0, len = s.length();
	  vector<int> track(256,0);
	  int tlen = 1;
	  for (int j = 0; j < len; j++) {
	    int k = 0, m = 0;
	    while (k < tlen) {
	      auto action = state[track[k]+(s[j]-'0')];
	      count += action.second;
	      if (action.first >= 0) track[m++] = action.first;
	      k++;
	    }
	    track[m] = 0; tlen = m+1;
	  }
	  cout << count << endl;
	}
	return 0;
}

Two Two C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;

public class AhoCorasick
{
    private int PowerOf2Counter = 0;
    private Trie GoTo;

    public AhoCorasick(IEnumerable<string> patterns)
    {
        GoTo = new Trie(patterns);
        initializeFail();
    }

    public void match(String text)
    {
        PowerOf2Counter = 0;
        var state = GoTo.Root;
        for (int i = 0; i < text.Length; i++)
        {
            char chr = text[i];

            while (IsFail(state, chr))
            {
                state = state.FailNode;
            }
            state = GoToFunc(state, chr);

            PowerOf2Counter += state.Output.Count;
        }
        Console.WriteLine(PowerOf2Counter);
    }

    private void initializeFail()
    {
        var queue = new Queue<Trie.Node>();

        foreach(var edge in GoTo.Root.Edges)
        {
            if (edge == null) continue;

            var childNode = edge;
            queue.Enqueue(childNode);
            childNode.FailNode = GoTo.Root;
        }

        while(queue.Count > 0)
        {
            var curNode = queue.Dequeue();

            for(int i=0;i<10;i++)
            {

                var childNode = curNode.Edges[i];
                if (childNode == null) continue;
                queue.Enqueue(childNode);

                var digit = new Trie.Digit() { Index = i };

                var failNode = curNode.FailNode;
                while(IsFail(failNode, digit))
                {
                    failNode = failNode.FailNode;
                }

                var newFailNode = GoToFunc(failNode, digit);
                childNode.FailNode = newFailNode;

                foreach (var o in newFailNode.Output)
                    childNode.Output.AddLast(o);
            }
        }
    }
    
    protected bool IsFail(Trie.Node state, Trie.Digit digit)
    {
        if (state == GoTo.Root)
        {
            return false;
        }

        return state.Edges[digit.Index] == null;
    }

    protected Trie.Node GoToFunc(Trie.Node state, Trie.Digit digit)
    {
        if ((state == GoTo.Root) && (GoTo.Root.Edges[digit.Index] == null))
        {
            return GoTo.Root;
        }

        return state.Edges[digit.Index];
    }
}

public class Trie
{
    public struct Digit
    {
        public static implicit operator Digit(char c)
        {
            return new Digit() { Index = c - 48 };
        }
        public int Index;
    }

    public class Node
    {
        public string Number;
        public Node FailNode;
        public LinkedList<string> Output = new LinkedList<string>();
        public Node[] Edges = new Node[10];
    }

    public Node Root = new Node();

    public Trie(IEnumerable<string> numbers)
    {
        foreach(var number in numbers)
        {
            var node = Root;
            for (int len = 1; len <= number.Length; len++)
            {
                var digit = (Digit)number[len - 1];
                Node next = node.Edges[digit.Index];
                if (next == null)
                {
                    next = new Node();
                    if (len == number.Length)
                    {
                        next.Number = number;
                    }
                    node.Edges[digit.Index] = next;
                }
                node = next;
            }

            node.Output.AddLast(number);
        }
    }
}

class Solution 
{
    static void Main(String[] args)
    {
        var allPowersOf2 = Enumerable.Range(0, 801).Select(pow => BigInteger.Pow(2, pow).ToString());

        var ac = new AhoCorasick(allPowersOf2);

        var T = Convert.ToInt32(Console.ReadLine());
        for(int i=0; i<T;i++)
        {
            var S = Console.ReadLine();
            ac.match(S);
        }
    }
}

Two Two Java Solution

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

Two Two JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the twoTwo function below.
 */
function twoTwo(a) {
    let i, j, t = '1', r = 0, n = 801;
    for (i = 1; i <= n && t.length <= a.length; i++) {
        j = a.indexOf(t);
        while (j > -1) {
            r++;
            j = a.indexOf(t, j + 1);
        }
        t = next2(t);
    }
    return r;

    function next2(a) {
        let v = '', i, n = a.length, s, c = 0;
        for (i = n - 1; i >= 0; i--) {
            s = (a.charAt(i) - 0) * 2 + c;
            v = (s % 10) + v;
            c = Math.floor(s / 10);
        }
        if (c > 0) v = c + v;
        return v;
    }
}
function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const a = readLine();

        let result = twoTwo(a);

        ws.write(result + "\n");
    }

    ws.end();
}

Two Two Python Solution

#!/bin/python3

import os
import sys

try:
    from profiler import line_profile
except:
    pass


HASH_MOD = 123412343
POWERS = []
DIM = 4
DIM_POW = 10 ** DIM
TWO_HASHES = {}
PRECALC = {}


# @line_profile()
def init():
    POWERS.append(1)
    for _ in range(100 * 1000 + 10):
        POWERS.append((POWERS[-1] * 29) % HASH_MOD)

    for x in range(DIM_POW):
        TWO_HASHES[str(x).zfill(DIM)] = None, None

    t = 1
    max_l = 0
    for _ in range(801):
        s = str(t)
        h = 0
        for ind, c in enumerate(s):
            h = (h + POWERS[ind] * int(c)) % HASH_MOD

        if len(s) >= DIM:
            prefix = s[:DIM]
            TWO_HASHES[prefix] = (h, len(s))
            # max_l = max(max_l, len(TWO_HASHES[prefix]))

        t *= 2
    # print(max_l)
    # raise

    for n in range(DIM_POW // 10):
        s = str(n)
        PRECALC[s] = 0
        while len(s) < DIM - 1:
            s = '0' + s
            PRECALC[s] = 0

    for n in range(DIM_POW // 10):
        n2 = n
        while n2:
            if (n2 & (n2 - 1)) == 0:
                PRECALC[str(n)] += 1

            n2 //= 10


# @line_profile()
def twoTwo(a):
    ans = 0

    a_hashes = [0] * (len(a) + 1)
    for ind, c in enumerate(a):
        a_hashes[ind + 1] = (a_hashes[ind] + POWERS[ind] * (ord(c) - 48)) % HASH_MOD
        ans += PRECALC[a[ind:ind + DIM - 1]]

    la = len(a_hashes)
    for ind in range(len(a) - DIM + 1):
        h, l = TWO_HASHES[a[ind:ind + DIM]]
        if (l is not None and
                ind + l < la):
            if (a_hashes[ind + l] - a_hashes[ind] - h * POWERS[ind]) % HASH_MOD == 0:
                ans += 1

    return ans


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    import time
    start = time.time()

    init()

    # print(time.time() - start)
    start = time.time()

    # import sys
    # fptr = sys.stdout
    # sys.stdin = open('input', 'r')

    t = int(input())

    for t_itr in range(t):
        a = input()

        result = twoTwo(a)

        fptr.write(str(result) + '\n')

    # print(time.time() - start)
    start = time.time()

    fptr.close()

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python