# Hackerrank Square Ten Tree problem solution

In this tutorial we are going to solve or make an solution of Square-Ten Tree problem. so here we have given the borders of array subsegment and we need to find its decomposition into a minimal number of nodes of a square ten tree.

## Problem solution in Python programming.

```# Enter your code here. Read input from STDIN. Print output to STDOUT
class Big:
def __init__(self, v):
self.value = self.check_zero(v)
self.size = 5000
self.size2 = 10 ** self.size

def modd(self, length, base0=False):
vv = self.check_zero(self.value[-length:])
if vv == '':
if base0:
return ''
else:
return '1' + '0' * length
return self.check_zero(self.value[-length:])

def mod_rest(self, length, is_plus):
vv = self.check_zero(self.value[-length:])

self.value = self.value[:-length]
if is_plus:
if not vv == '':
self.value = self.plus(self.value, '1')

def plus(self, value1, value2):
result = ""
size = self.size
size2 = self.size2
length = (max(len(value1), len(value2)) // size + 1) * size

value1 = '0' * (length - len(value1)) + value1
value2 = '0' * (length - len(value2)) + value2
rest = 0

for j in range(length, 0, -size):
v1 = int(value1[j - size: j])
v2 = int(value2[j - size: j])
r = v1 + v2 + rest
if r >= size2:
rest = 1
r -= size2
else:
rest = 0
result = '0' * (size - len(str(r))) + str(r) + result

if rest > 0:
result = str(rest) + result
result = self.check_zero(result)

return result

def minus(self, value1, value2):
# value1 - value2, len(value1) >= len(value2)
result = ""
size = self.size
size2 = self.size2
length = (max(len(value1), len(value2)) // size + 1) * size

value1 = '0' * (length - len(value1)) + value1
value2 = '0' * (length - len(value2)) + value2
rest = 0

for j in range(length, 0, -size):
v1 = int(value1[j - size: j])
v2 = int(value2[j - size: j])
r = v1 - v2 + rest
if r < 0:
rest = -1
r += size2
else:
rest = 0
result = '0' * (size - len(str(r))) + str(r) + result

result = self.check_zero(result)

return result
def compare(self, length):
return len(self.value) - length

def check_zero(self, k):
# if len(k) == 0:
#     return k
strr = ''
for j in range(len(k)):
if k[j] == '0':
continue
else:
strr = k[j:]
break
return strr

def main(l, r):
ll = Big(l)
rr = Big(r)

indexs = [1, 1]
results1 = []
results2 = []
# print(ll.value, rr.value)
ll.value = ll.minus(ll.value, '1')
while True:
index = indexs[-2]
if ll.compare(index) <= 0 and rr.compare(index) <= 0:
results1.append(ll.minus(rr.value, ll.value))
# print(len(results1) - 1, ll.value, rr.value, results1[-1])
break
else:
l1 = ll.minus('1' + '0' * index, ll.modd(index))
# l1 = ll.plus(l1, '1')
r1 = rr.modd(index, True)
# print(len(results1), ll.value, rr.value, l1, r1, index)
ll.mod_rest(index, True)
rr.mod_rest(index, False)
results1.append(l1)
results2.append(r1)

indexs.append(indexs[-1] << 1)
# print(results1, results2)
final = []
for n, k in enumerate(results1):
strr = ll.check_zero(k)
if not strr == '':
final.append([n, strr])

for m in range(len(results2) - 1, -1, -1):

strr = ll.check_zero(results2[m])
if not strr == '':
final.append([m, strr])

print(len(final))

for ii in range(len(final)):
print(final[ii][0], final[ii][1])

if __name__ == '__main__':
main(input(), input())```

## Problem solution in Java Programming.

```import java.util.Scanner;
import java.util.Arrays;

// I recommend skipping this problem. The problem statement is way too convoluted.
// However, here are some takeaway concepts from this problem:
//   - Implementing a custom BigInt as a byte[]
//   - Implementing log2(int n)
//   - Realizing that our algorithm can process the giant numbers in portions

// - Runtime: O(n + m) where n = # of digits in L, m = # of digits in R (for interval [L,R]).
// - Numbers can literally have millions of digits in this problem. An "int" or "long" is not big enough to store these numbers. Although Java's BigInteger is big enough, it turns out to be too slow for this problem. I wrote a custom "BigInt" class to speed up calculations.
// - To achieve linear runtime, we need an algorithm that splits up these giant numbers into portions and processes them separately. A great way to do this is to split by level, as done below.
// - This was a very difficult problem. You must have both linear runtime and efficient code to pass all testcases.
public class Solution {
public static void main(String[] args) {
/* Read and save input */
Scanner scan = new Scanner(System.in);
String strL  = new BigInt(scan.next()).subtract(BigInt.ONE).toString(); // subtract 1 since it's [L,R] inclusive
String strR  = scan.next();
scan.close();

/* Calculate interval sizes (by just saving # of digits) */
int [] intervalDigits = new int[log2(strR.length()) + 3]; // The +3 gives us an estimate of the size we need
for (int k = 0; k < intervalDigits.length; k++) {
intervalDigits[k] = digitsInInterval(k);
}

/* Initialize variables */
StringBuilder sb      = new StringBuilder();
int endL              = strL.length();
int endR              = strR.length();
BigInt upperBound     = BigInt.ONE;
boolean carry         = false;
boolean lastIteration = false;
int blockCount        = 0;
int level             = 0;

/* Calculate counts for increasing segment sizes */
while (!lastIteration) {
/* Get portion of each String corresponding to current level */
int numDigits   = intervalDigits[level + 1] - intervalDigits[level];
int startL      = Math.max(endL - numDigits, 0);
int startR      = Math.max(endR - numDigits, 0);
BigInt numL = (endL == 0) ? BigInt.ZERO : new BigInt(strL.substring(startL, endL));
if (carry) {
}

/* Calculate upper bound */
if (startR == 0) {
upperBound = new BigInt(strR.substring(startR, endR));
lastIteration = true;
} else {
upperBound = BigInt.tenToPower(numDigits);
}

/* If not skipping this level, process it */
if ((!numL.equals(BigInt.ZERO) && !numL.equals(upperBound)) || startR == 0) {
BigInt count = upperBound.subtract(numL);
carry = true;
blockCount++;
sb.append(level + " " + count +  "\n");
}

/* Update variables for next iteration */
endL = startL;
endR = startR;
level++;
}

StringBuilder sb2 = new StringBuilder();
level             = 0;
endR              = strR.length();

/* Calculate counts for decreasing segment sizes */
while (true) {
/* Calculate number of nodes in current level */
int numDigits = intervalDigits[level + 1] - intervalDigits[level];
int startR    = Math.max(endR - numDigits, 0);
if (startR == 0) {
break;
}
BigInt count = new BigInt(strR.substring(startR, endR));

/* If not skipping this level, process it */
if (!count.equals(BigInt.ZERO)) {
blockCount++;
sb2.insert(0, level + " " + count +  "\n");
}

/* Update variables for next iteration */
endR = startR;
level++;
}

System.out.println(blockCount + "\n" + sb + sb2);
}

static int log2(int n) { // assumes positive number
}

static int digitsInInterval(int k) {
if (k == 0) {
return 1;
} else {
return (int) (Math.pow(2, k - 1) + 1);
}
}
}

// - Java's BigInteger is not fast enough to pass the testcases. The BigInt I create below is more efficient for this problem.
// - This link has good implementation ideas (Though they store numbers in reverse order):
// - BigInt numbers may be stored with leading 0s
// - BigInt only works with non-negative integers
class BigInt {
public static final BigInt ZERO = new BigInt("0");
public static final BigInt ONE  = new BigInt("1");

public final byte[] digits; // will use 8 bits per digit for simplicity, even though 4 bits is enough

/* Constructor */
public BigInt(String str) {
digits = new byte[str.length()];
for (int i = 0; i < digits.length; i++) {
digits[i] = Byte.valueOf(str.substring(i, i + 1));
}
}

/* Constructor */
public BigInt(byte [] digits) {
this.digits = digits;
}

public static BigInt tenToPower(int exponent) {
byte [] digits = new byte[exponent + 1];
digits[0] = 1;
return new BigInt(digits);
}

byte [] digitsA = digits;
byte [] digitsB = other.digits;

/* Create new Array to hold answer */
int newLength = Math.max(digitsA.length, digitsB.length);
if (!(digitsA[0] == 0 && digitsB[0] == 0)) {
newLength++;
}
byte [] result = new byte[newLength];

int carry = 0;
int ptrA = digitsA.length - 1;
int ptrB = digitsB.length - 1;
int ptrR = result.length  - 1;

while (ptrA >= 0 || ptrB >= 0 || carry > 0) {
int sum = carry;
if (ptrA >= 0) {
sum += digitsA[ptrA--];
}
if (ptrB >= 0) {
sum += digitsB[ptrB--];
}
result[ptrR--] = (byte) (sum % 10);
carry          = sum / 10;
}
return new BigInt(result);
}

public BigInt subtract(BigInt other) { // assumes "other" is smaller than this BigInt
byte [] digitsB = other.digits;
byte [] result  = Arrays.copyOf(digits, digits.length); // copy of "digitsA"

/* Do the subtraction */
int ptrB = digitsB.length - 1;
int ptrR = result.length  - 1;
while (ptrB >= 0 && ptrR >= 0) {
result[ptrR] -= digitsB[ptrB];
/* if necessary, do the "borrow" */
if (result[ptrR] < 0) {
result[ptrR] += 10;
int ptrBorrow = ptrR - 1;
while (result[ptrBorrow] == 0) {
result[ptrBorrow--] = 9;
}
result[ptrBorrow]--;
}
ptrB--;
ptrR--;
}
return new BigInt(result);
}

@Override
public boolean equals(Object other) {
if (!(other instanceof BigInt)) {
return false;
}

byte [] digitsA = digits;
byte [] digitsB = ((BigInt) other).digits;

int indexA = 0;
int indexB = 0;

while (indexA < digitsA.length && digitsA[indexA] == 0) {
indexA++;
}
while (indexB < digitsB.length && digitsB[indexB] == 0) {
indexB++;
}

/* If lengths not equal, BigInts aren't equal */
int lenA = digitsA.length - indexA;
int lenB = digitsB.length - indexB;

if (lenA != lenB) {
return false;
}

/* Check to see if all digits match for the 2 BigInts */
while (indexA < digitsA.length && indexB < digitsB.length) {
if (digitsA[indexA++] != digitsB[indexB++]) {
return false;
}
}
return true;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
int i = 0;

while (i < digits.length && digits[i] == 0) {
i++;
}

/* Special Case: the BigInt 0 */
if (i == digits.length) {
return "0";
}

/* Create and return String */
for (  ; i < digits.length; i++) {
sb.append(digits[i]);
}
return sb.toString();
}
}```

### Problem solution in C++ programming.

```#include <bits/stdc++.h>
#define pb push_back
#define sqr(x) (x)*(x)
#define sz(a) int(a.size())
#define reset(a,b) memset(a,b,sizeof(a))
#define oo 1000000007

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

char l[1000007],r[1000007];
int m,n;

void plus1(int pos){
int t=1;
for(int i=pos; i>=1; --i){
if(l[i]=='9') l[i]='0';
else{
++l[i];
break;
}
}
}

vector<int> sub9(int s, int f){
int t=0;
vector<int> ans;
for(int i=f; i>=s; --i){
int v='0'-l[i]-t;
if(v<0){
v+=10;
t=1;
}else{
t=0;
}
ans.pb(v);
}
return ans;
}

vector<int> sub(int s, int f){
int t=0;
vector<int> ans;
for(int i=f; i>=s; --i){
int v=r[i]-l[i]-t;
if(v<0){
v+=10;
t=1;
}else{
t=0;
}
ans.pb(v);
}
return ans;
}

while(sz(a)<sz(b)) a.pb(0);
while(sz(b)<sz(a)) b.pb(0);
vector<int> c;
int t=0;
for(int i=0; i<sz(a); ++i){
int v=a[i]+b[i]+t;
c.pb(v%10);
t=v/10;
}
if(t>0) c.pb(t);
return c;
}

void printVector(vector<int> &a){
for(int i=sz(a)-1; i>=0; --i) printf("%d",a[i]);
}

struct Block{
int s;
vector<int> cnt;
Block(){}
Block(int _s, vector<int> &_cnt){
s = _s;
cnt = _cnt;
while(sz(cnt)>1 && cnt[sz(cnt)-1]==0) cnt.pop_back();
}
};
vector<Block> result;

int main(){
//    freopen("input.txt","r",stdin);
scanf("%s",l+1);
m=strlen(l+1);
scanf("%s",r+1);
n=strlen(r+1);
for(int i=n; i>=n-m+1; --i) l[i]=l[i-(n-m)];
for(int i=n-m; i>=1; --i) l[i]='0';

int x=0;
while(x<=n && l[x+1]==r[x+1]) ++x;
if(x>n){
puts("1");
puts("0 1");
return 0;
}
while(x<n){
if(x==n-1){
vector<int> cnt; cnt.pb(r[n]-l[n]+1);
result.pb(Block(0,cnt));
l[n]=r[n];
break;
}else if(l[n]!='1'){
vector<int> cnt; cnt.pb(0);
while(l[n]!='1'){
plus1(n);
++cnt[0];
while(x<n && l[x+1]==r[x+1]) ++x;
if(x==n){
++cnt[0];
break;
}
}
result.pb(Block(0,cnt));
}else{
int u=n-1;
while(u-1>x && l[u]=='0') --u;
int len=n-u;
int s=1;
while((1<<(s)) <= len) ++s;
int leftBound = n - (1<<(s));
int rightBound = n - (1<<(s-1));
leftBound = max(leftBound,0);
if(x < leftBound){
vector<int> cnt = sub9(leftBound+1,rightBound);
result.pb(Block(s, cnt));
for(int i=leftBound+1; i<=rightBound; ++i) l[i]='0';
l[n]='0';
plus1(leftBound);
}else{
vector<int> cnt = sub(leftBound+1, rightBound);
result.pb(Block(s, cnt));
for(int i=leftBound+1; i<=rightBound; ++i) l[i]=r[i];
l[n]='0';
}
while(x<n && l[x+1]==r[x+1]) ++x;
if(x<n) l[n]='1';
}
}
printf("%d\n",sz(result));
for(int i=0; i<sz(result); ){
int j=i;
vector<int> sum = result[i].cnt;
while(j+1<sz(result) && result[j+1].s==result[i].s){
sum = t;
}
printf("%d ",result[i].s);
printVector(sum);
i=j+1;
puts("");
}
}```

### Problem solution in C programming.

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

#define DIGIT(a) ((a) - '0')
#define  CHAR(a) ((a) + '0')

char L[1000002];
char R[1000002];
char amount[1000002];

int main()
{
int    lvls[42];
char * amts[42] = {0};
int    lenL, lenR, diff1, left, right, pos, groupsz, level, max, rmd, carry, i, n = 0;

scanf("%s", L);
scanf("%s", R);

lenL = strlen(L);
lenR = strlen(R);

if (lenL < lenR)
{
memmove(L + lenR - lenL, L, lenL + 1);
memset(L, '0', lenR - lenL);
lenL = lenR;
}

for (i = 0; i < lenL; ++i)
if (L[i] != R[i]) break;
diff1 = i;

if (diff1 >= lenL-1)
{
printf("1\n0 %d\n", 1 + R[lenR-1] - L[lenL-1]);
return 0;
}

level = 0;

if (L[lenL-1] == '0')
{
L[lenL-1] = '1';
lvls[n] = level;
amts[n] = malloc(1 + 1);
if (amts[n] == NULL)
return 1;
strcpy(amts[n], "1");
n++;
}
else if (L[lenL-1] != '1')
{
lvls[n] = level;
amts[n] = malloc(1 + 1);
if (amts[n] == NULL)
return 1;
amts[n][0] = CHAR(11 - DIGIT(L[lenL-1]));
amts[n][1] = '\0';
n++;
for (pos = lenL-2; L[pos] == '9'; --pos)
;
L[pos] += 1;
for (i = pos+1; i < lenL; ++i)
L[i] = '0';
}

groupsz = 1;
left = right = lenL-2;

while (diff1 < left)
{
level += 1;
rmd = 0;
max = '0';
for (i = right; i >= left; --i)
{
if (L[i] > max) max = L[i];
rmd -= DIGIT(L[i]);
if (rmd < 0)
{
amount[i] = CHAR(rmd + 10);
rmd = -1;
}
else
{
amount[i] = CHAR(rmd);
rmd = 0;
}
}

if (max > '0')
{
for (pos = left-1; L[pos] == '9'; --pos)
;
L[pos] += 1;
for (i = pos+1; i <= right; ++i)
L[i] = '0';

lvls[n] = level;
amts[n] = malloc(groupsz + 1);
if (amts[n] == NULL)
return 1;
memcpy(amts[n], &amount[left], groupsz);
amts[n][groupsz] = '\0';
n++;
}

right -= groupsz;
groupsz *= 2;
left = MAX(0, right - groupsz + 1);
}

/* take truncated/diff group */
level += 1;
rmd = 0;
max = '0';
for (i = right; i >= left; --i)
{
rmd += R[i] - L[i];
if (rmd < 0)
{
amount[i] = CHAR(rmd + 10);
rmd = -1;
}
else
{
amount[i] = CHAR(rmd);
rmd = 0;
}

if (amount[i] > max) max = amount[i];
}

if (max > '0')
{
lvls[n] = level;
amts[n] = malloc(right + 1 - left + 1);
if (amts[n] == NULL)
return 1;
memcpy(amts[n], &amount[left], right + 1 - left);
amts[n][right+1-left] = '\0';
n++;
}

left = right + 1;
groupsz /= 2;
right = left + groupsz - 1;

while (left < lenR-1)
{
level -= 1;
max = '0';
for (i = left; i <= right; ++i)
if (R[i] > '0') max = R[i];

if (max > '0')
{
if (lvls[n-1] == level)
{
/* add amount to amts[n-1] */
carry = 0;
for (i = right; i >= left; --i)
{
carry += DIGIT(R[i]) + DIGIT(amts[n-1][i-left]);
if (carry >= 10)
{
amount[i] = CHAR(carry - 10);
carry = 1;
}
else
{
amount[i] = CHAR(carry);
carry = 0;
}
}
if (carry)
{
amount[i] = '1';
free(amts[n-1]);
amts[n-1] = malloc(1 + groupsz + 1);
if (amts[n-1] == NULL)
return 1;
memcpy(amts[n-1], &amount[i], 1 + groupsz);
amts[n-1][1+groupsz] = '\0';
}
else
{
memcpy(amts[n-1], &amount[left], groupsz);
}
}
else
{
lvls[n] = level;
amts[n] = malloc(groupsz + 1);
if (amts[n] == NULL)
return 1;
memcpy(amts[n], &R[left], groupsz);
amts[n][groupsz] = '\0';
n++;
}
}

left = right + 1;
groupsz /= 2;
right = left + groupsz - 1;
}

if (R[lenR-1] > '0')
{
level = 0;
if (lvls[n-1] == level)
{
/* add amount to amts[n-1] */
carry = DIGIT(R[lenR-1]) + DIGIT(amts[n-1][0]);
if (carry >= 10)
{
free(amts[n-1]);
amts[n-1] = malloc(2 + 1);
if (amts[n-1] == NULL)
return 1;
sprintf(amts[n-1], "%d", carry);
}
else
{
amts[n-1][0] = CHAR(carry);
}
}
else
{
lvls[n] = level;
amts[n] = malloc(1 + 1);
if (amts[n] == NULL)
return 1;
amts[n][0] = R[lenR-1];
amts[n][1] = '\0';
n++;
}
}

printf("%d\n", n);
for (i = 0; i < n; ++i)
{
for (left = 0; amts[i][left] == '0'; ++left)
;
printf("%d %s\n", lvls[i], &amts[i][left]);
}

return 0;
}```