2

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.

6
  • Isn't 4, 5 children of 2 only? 6 shouldn't be child of 2, since there is at most two children, at positions 2i+1 and 2i+2.
    – Daniel
    Jul 8, 2020 at 17:49
  • It sounds like the exercise is using the word "sibling" to mean something other than it usually means. Can you confirm what exactly it means?
    – Joni
    Jul 8, 2020 at 17:54
  • @Daniel, I added explanation, can you please check now
    – learner
    Jul 8, 2020 at 17:55
  • @Joni, I added explanation, is that helpful?
    – learner
    Jul 8, 2020 at 17:56
  • This data structure is known as an array-based heap. There is one root node at index 0. Two children of the root at 1,2. Four children at 3,4,5,6. Then eight, then sixteen. So given an index into the array, you need to compute the number of parents starting at that index. Given the number of parents, you can compute the starting and ending index for that level of the heap. If the ending index is beyond the end of the heap, then adjust it. Then simply print all the array elements between the starting and ending indexes. Jul 8, 2020 at 18:00

3 Answers 3

1

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.
1

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();
  }
1
  • Start index is largest power of 2 of position of value and double of start index -1 is end index I am not able to understand this point, can you please explain how is this possible? Also start = Integer.highestOneBit(pos); How this gives us max power of 2, I have seen the highestOneBit ind javadoc but not able to co-relate this here.
    – learner
    Jul 20, 2020 at 22:30
0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.