fork(9) download
copy 
  1. import java.util.Arrays;
  2. import java.util.HashMap;
  3. import java.util.Map;
  4. import java.util.stream.IntStream;
  5.  
  6. class Answer {
  7.  
  8.     private static final int parent(int height, int node) {
  9.         int size = (int)Math.pow(2, height) - 1;
  10.  
  11.         if (node == size) {
  12.             return -1;
  13.         }
  14.  
  15.         int before = 0;
  16.         do {
  17.             if (size == 0) {
  18.                 throw new IllegalStateException();
  19.             }
  20.             size >>>= 1;
  21.             int left = before + size;
  22.             int right = left + size;
  23.             int me = right + 1;
  24.             if (left == node || right == node) {
  25.                 return me;
  26.             }
  27.             if (node > left) {
  28.                 before = left;
  29.             }
  30.         } while (true);
  31.  
  32.     }
  33.  
  34.     public static final int[] answerToo(int height, int[] nodes) {
  35.         return IntStream.of(nodes).map(n -> parent(height, n)).toArray();
  36.     }
  37.  
  38.     public static final int[] answer(int height, int[] nodes) {
  39.         int[] ans = new int[nodes.length];
  40.         Map<Integer, Integer> indices = new HashMap<>();
  41.         IntStream.range(0, nodes.length).forEachOrdered(i -> indices.put(nodes[i], i));
  42.         int next = postOrder(height, 0, 0, indices, ans);
  43.         if (next < 0) {
  44.             int i = indices.get(-next);
  45.             ans[i] = -1;
  46.         }
  47.         return ans;
  48.     }
  49.  
  50.     private static int postOrder(int limit, int depth, int next, Map<Integer, Integer> indices, int[] ans) {
  51.         if (depth == limit) {
  52.             return next;
  53.         }
  54.         // left
  55.         int left = postOrder(limit, depth + 1, next, indices, ans);
  56.         next = left < 0 ? -left : left;
  57.         int right = postOrder(limit, depth + 1, next, indices, ans);
  58.         next = right < 0 ? -right : right;
  59.  
  60.         int me = next + 1;
  61.  
  62.         if (left < 0) {
  63.             int i = indices.get(-left);
  64.             ans[i] = me;
  65.         }
  66.         if (right < 0) {
  67.             int i = indices.get(-right);
  68.             ans[i] = me;
  69.         }
  70.  
  71.         return indices.containsKey(me) ? -me : me;
  72.  
  73.     }
  74.  
  75.     public static void main(String[] args) {
  76.         testRun(3, new int[] { 7, 3, 5, 1 }, new int[] { -1, 7, 6, 3 });
  77.         testRun(5, new int[] { 19, 14, 28 }, new int[] { 21, 15, 29 });
  78.     }
  79.  
  80.     private static void testRun(int height, int[] input, int[] output) {
  81.         int[] ans = answer(height, input);
  82.         int[] ans2 = answerToo(height, input);
  83.         System.out.printf("Input height %d and nodes %s:\n%s\n%s\n", height, Arrays.toString(input),
  84.                 Arrays.toString(ans), Arrays.toString(ans2), Arrays.toString(output));
  85.     }
  86.  
  87. }
  88.  
Success #stdin #stdout 0.1s 711680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Input height 3 and nodes [7, 3, 5, 1]:
[-1, 7, 6, 3]
[-1, 7, 6, 3]
Input height 5 and nodes [19, 14, 28]:
[21, 15, 29]
[21, 15, 29]
https://ideone.com/qiwPtR
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!