HackerRank Two Two problem solution

In this 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.

HackerRank Two Two problem solution in 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])

Two Two problem solution in 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));
    }
}

Problem solution in 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;
}

Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();

struct trie
{
  struct trie *next[10];
  char end[10];
} t;

static char po2[100000];
static int po2_len=1;

void add_to_trie()
{
  int j;
  struct trie *curt = &t;
  struct trie *newt;
  for (j=po2_len-1; j>=0; j--)
  {
    if(curt->next[po2[j]]==NULL)
    {
      newt = calloc(1, sizeof(struct trie));
      curt->next[po2[j]] = newt;      
    }
    if(j == 0)
      curt->end[po2[0]] = 1;
    curt = curt->next[po2[j]];
  }
}

void double_po2()
{
  int i=0, carry=0, sum=0;
  while(i<po2_len)
  {
    sum = po2[i] + po2[i] + carry;
    po2[i] = sum % 10;
    carry = sum/10;
    i++;
  }
  if(carry != 0)
  {
    po2[po2_len++] = carry;
  }
}
void generate_trie()
{
  po2[0]=1;
  int i;
  for(i=0; i<10; i++)
  {
    t.next[i]=NULL;
    t.end[i]=0;
  }
  add_to_trie();
  for(i=1; i<=800;i++)
  {
    double_po2();
    add_to_trie();  
  }
}

/*
 * Complete the twoTwo function below.
 */
int twoTwo(char* a) {
  int i, j, slen = strlen(a), curdig;
  struct trie *curt;  
  int total_po2 = 0;
  for(i = 0; i < slen; i++)
  {//find po2 at pos i
    curt = &t;
    curdig = a[i] - '0';
    if (curt->end[curdig] == 1)
      total_po2++;
    j = i;
    while(j<slen)
    {
      if(curt->next[curdig] == NULL)
        break;
      curt = curt->next[curdig];
      j++;
      if(j<slen)
      {
        curdig = a[j]-'0';
        if(curt->end[curdig] == 1)
          total_po2++;
      }
    }
  }
  return total_po2;

}

int main()
{

    generate_trie();

    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* t_endptr;
    char* t_str = readline();
    int t = strtol(t_str, &t_endptr, 10);

    if (t_endptr == t_str || *t_endptr != '') { exit(EXIT_FAILURE); }

    for (int t_itr = 0; t_itr < t; t_itr++) {
        char* a = readline();

        int result = twoTwo(a);

        fprintf(fptr, "%dn", result);
    }

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == 'n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == 'n') {
        data[data_length - 1] = '';
    }

    data = realloc(data, data_length);

    return data;
}