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) {
            numL = numL.add(BigInt.ONE);
        }

        /* 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
    return 31 - Integer.numberOfLeadingZeros(n);
}

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): // http://iwillgetthatjobatgoogle.tumblr.com/post/32583376161/writing-biginteger-better-than-jdk-one // - 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);
}

public BigInt add(BigInt other) {
    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];

    /* Do the addition */
    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;

    /* Remove leading 0s */
    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;

    /* Skip leading 0s */
    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();
}

}

Hackerrank should enable GMP and BCMath functions on their PHP servers to enable PHP users solve problems involving big integers. These functions are integral part of PHP and they used to work before on their servers but suddenly started giving error messages "function not defined" when trying to use any of the functions. I think they did an upgrade and just forgot to enable the functions again.

My solution passed test cases 0 to 32 but failed on other test cases ("wrong answer", not timeout) Can someone give the input of any of those test cases (e.g test case 50) so that I can debug my code? Thanks in advance

Hey can someone help me out solving these problems? My friend sent this contest to me. He says its for noobs but I dont think it is. I cant solve it without any help because I'm new to competitive programming. Here is the contest: https://www.hackerrank.com/newbie-challenge

java code:

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

vector<int> add(vector<int> &a, vector<int> &b){
    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){
            vector<int> t=add(sum, result[++j].cnt);
            sum = t;
        }
        printf("%d ",result[i].s);
        printVector(sum);
        i=j+1;
        puts("");
    }
}