Mocoder
BAN USERUsing a BFS you can find it. You don't care about the path but length of the path when performing the search.
function find_ancesstor (tree, a, b) {
var shortest_distance = Infinity;
var result = null;
traverse(tree, []);
return result.data;
function traverse (node) {
if(!node) return;
var distance = find_distance(node, a, b);
if(distance && distance < shortest_distance){
shortest_distance = distance;
result = node;
}
traverse(node.left);
traverse(node.right);
}
}
function find_distance (node, a, b) {
var distance_a = null,
distance_b = null;
traverse(node, 0)
function traverse (node, distance) {
if(!node) return;
if(node.data == a){
distance_a = distance;
}
if(node.data == b){
distance_b = distance;
}
distance += 1;
traverse(node.left, distance);
traverse(node.right, distance);
}
if(distance_a && distance_b){
return distance_a + distance_b;
}
return null;
}
// 8
// 4 12
// 2 6 10 14
// 1 3 5 7 9 11 13 15
var tree = {"data":8,"left":{"data":4,"left":{"data":2,"left":
{"data":1,"left":null,"right":null},"right":{"data":3,
"left":null,"right":null}},"right":{"data":6,"left":
{"data":5,"left":null,"right":null},"right":{"data":7,
"left":null,"right":null}} },"right":{"data":12,"left":
{"data":10,"left":{"data":9,"left":null,"right":null},
"right":{"data":11,"left":null,"right":null}},"right":
{"data":14,"left":{"data":13,"left":null,"right":null},
"right":{"data":15,"left":null,"right":null}} }};
console.log(find_ancesstor(tree, 9, 11));
You can get number of digits of a number without converting it to string but I will do it that way because JavaScript.
If you have number of digits then your index can be calculated like this:
For example for index of 102 you have:
9 x 1 digit
(90) x 2 digits
2 x 3digits
which is equal
(9*1)+(90*2)+(2*3)
function indexOf(number){
var result = 0;
var digits = number.toString().length;
for(var i =1; i<digits; i++){
result += i * 9 * (Math.pow(10,i-1)) ;
}
var remaining = number - Math.pow(10, digits-1);
result += digits * remaining;
return result;
}
JavaScript Solution:
function find(lists) {
"use strict";
// Sort lists
lists = lists.map(function (list) {
return list.sort(function(a,b) {return a-b;});
});
// Find all possible ranges
var ranges = [];
lists.forEach(function (list, i) {
list.forEach(function (n) {
if(i+1 !== lists.length){
lists[i+1].forEach(function (m) {
if(n>m)
ranges.push([m,n]);
else
ranges.push([n,m]);
});
}
});
});
// filter out ranges that do not include one item from each list
ranges = ranges.filter(function checkRange (range) {
var n = range[0];
var m = range[1];
// Make a hash that is reperesnting lists.
var includesHash = lists.map(function () {
return false;
});
// for each integer from beginning of range to end of it
intloop: for(var i = n; i <= m; i++){
// for each list
listloop: for(var j = 0; j < lists.length; j++){
var list = lists[j];
// for each item of the list
itemloop: for(var k = 0; k< list.length; k++){
var item = list[k];
// if item equal to the integer we are checking against (i)
if(item === i){
// this list includes this number. break list loop
includesHash[j] = true;
break listloop;
}
}
}
}
// if all lists pass the test return true.
return includesHash.filter(function (includes) {
return includes === true;
}).length === lists.length;
});
// sort ranges by width of each range
ranges = ranges.sort(function (range1, range2) {
return (range1[1] - range1[0]) - (range2[1] - range2[0]);
});
// return smallest range
return ranges[0];
}
console.log(find([
[4, 10, 15, 24, 26],
[0, 9, 12, 20],
[5, 18, 22, 30]
]));
AD's answer is perfect. Here is a bit of explanation:
Imagine you have a signed 4 bit system. In that system
would be this:
Shift to right add a zero to beggining of sequence:
- Mocoder January 29, 2014