Get all possible nodes at same level for given position

user_3181365 0
Viewed 1080

Linear array with parent at i = 0 and children at 2i+1 and 2i+2

Find out all siblings of the person X. Return the sorted list of siblings.

If no siblings then return -1.

Example:

arr = 1,2,3,4,5,6
X = 5

Output: 4,6

    Explanation : 2,3 are children of 1. 
                  4,5 are children of 2.
                  6 are children of 3.
Here get children of 2 and 3 (because 3 is sibling of 2)  
So siblings of 5 are 4,6.

What is the correct way to solve this program.

algorithm java
3 Answers

If I read this question correctly, you want all indices of the same generation, not simply the same parent.

Index i belongs to generation floor(log base 2(i+1)).

index generation
0     0
1     1
2     1
3     2
4     2
5     2
6     2
7     3   etc...

The range of indices that belong to generation g for g > 0 are (2^g)-1 through (2^(g+1))-2. This doesn't apply to generation 0, which is just itself.

Then to find the sibling indices of a given index:

1. Find its generation
2. Find the range of indices for that generation 
3. Eliminate the input index
4. Truncate the range if it extents past the end of the array.

E.g. arr = 1,2,3,4,5,6
X = 5
i = index of 5 = 4.
g = floor(log base 2(5)) = 2
range = 3 through 6.
after eliminating the input and truncating, the valid indices are 3, 5.
values at these indices are 4, 6.
user_20410770

First, find the position of value. Then get sibling start index and end index in array. Start index is largest power of 2 of position of value and double of start index -1 is end index. Get the subarray and filter the value from array.

  public int[] getSiblings(int[] arr, int x) {
    int pos = 0;
    for (int i = 0; i < arr.length; i++) {
      if(arr[i]==x) pos = i+1;
    }
    int start = Integer.highestOneBit(pos); // get max power of 2
    int end = start*2-1 >= arr.length ? arr.length: start*2-1;
    return IntStream.range(start-1, end).map(i -> arr[i]).filter(v -> v!=x).toArray();
  }
user_42073060

As I understood, this is a problem about printing all elements in the same depth than X in the tree.

First find out the depth of X:

depth = floor(log2(X));

Now we have the depth of X. We just need print all elements in the same depth than X within the array. The i-th layer (of depth i) starts are position 2^i - 1, so:

if(depth == 0) {print(-1); return;}

int sibbling_count = 0;
for(int i = 2^depth - 1; i < 2^(depth + 1) - 1; i++){
    if(i < arr.size() && arr[i] != X){
         sibbling_count++;
         print(arr[i]);
    }
}
if(sibbling_count == 0) print(-1);
user_53488750
Related