Michael Lee Michael Lee - 3 days ago 6
Javascript Question

Buggy binary tree

I am attempting to solve codeforces 737A using javascript, which is doing a binary search of recrusing the tree of

2*x
and
10*x+1
, from given input
a
to another input
b
, but it seems that my program can only search through those nodes at
2*x
, and those
10*x+1
seems ignored. Interesting and WHY? Thanks.

var tt = readline().split(' ');
var a = parseInt(tt[0]);
var b = parseInt(tt[1]);

print(f([],a,b));
function f(arr,x,b){
if (x>b){
return [];
}else if (x==b){
return _add(arr,x);
}else{
return (f(_add(arr,x),(2*x),b) || f(_add(arr,x),(10*x+1),b));
}
}

function _add(array,x){
var _arr = array.slice();
_arr.push(x);
return _arr;
}

Answer

You need to return false instead of an empty array. The empty array resolves to true that means you iterate only the left branch.

(BTW, no need for else parts if then parts return.)

function go(a, b) {
    //var tt = readline().split(' ');
    //var a = parseInt(tt[0]);
    //var b = parseInt(tt[1]);

    function f(arr, x, b) {
        if (x > b) {
            return false; // no []!!!
        } 
        if (x == b) {
            return _add(arr, x);
        }
        return (f(_add(arr, x), (2 * x), b) || f(_add(arr, x), (10 * x + 1), b));
    }

    function _add(array, x) {
        var _arr = array.slice();
        _arr.push(x);
        return _arr;
    }

    return f([], a, b);
}
console.log(go(2, 162));
console.log(go(4, 42));
console.log(go(100, 40021));
.as-console-wrapper { max-height: 100% !important; top: 0; }

Comments