Buggy binary tree

Question

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

Nina Scholz · Accepted Answer · 2016-11-30 09:25:10Z

1

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

edited Nov 30, 2016 at 9:25

answered Nov 30, 2016 at 9:18

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Michael Lee Over a year ago

Thanks for your help, I have never noticed that [] is a truth value in javascript

slebetman · Accepted Answer · 2016-11-30 09:19:12Z

0

Two issues:

Truthiness. In javascript, falsy values are false, null, undefined, 0, NaN and empty strings (""). All other values are true.

You are returning an array for the base case:
```
return [];
```
So this will always be true.
How the || operator works. The || operator short-circuits. Therefore, if the left-hand value is truthy it will return it and not evaluate the right-hand code.

You wrote:
```
f(_add(arr,x),(2*x),b) || f(_add(arr,x),(10*x+1),b)
```
Since in all cases f() never return anything falsy that expression is basically:
```
true || f(_add(arr,x),(10*x+1),b)
```
As such the || operator never evaluates the 10*x+1 case.

To make the code work you need to either write a function to choose a non-empty array instead of using the || operator or make f() return false or 0 for the base case instead of an empty array (which may or may not break the algorithm, I don't know since I don't know the algorithm).

answered Nov 30, 2016 at 9:19

slebetman

115k19 gold badges147 silver badges180 bronze badges

4 Comments

Michael Lee Over a year ago

A problem: why ( [] == true ) returns false then?

slebetman Over a year ago

Not sure about that but [] is indeed truthy: if ([]) {console.log('HA')} prints "HA". The == operator is probably triggering some type conversion. Note that the || operator behaves like if rather than ==: [] || 'mango' returns [] not "mango" and [] || console.log('HA') does not print anything while [] && console.log('HA') prints "HA"

Michael Lee Over a year ago

It is interesting, how are == in javascript works the

slebetman Over a year ago

@MichaelLee: See: stackoverflow.com/questions/4923631/…

Collectives™ on Stack Overflow

Buggy binary tree

2 Answers 2

1 Comment

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related