4
$\begingroup$

The title could be a little bit confusing, and it is not easy to summarize it within a sentence, therefore I will explain it in detail below. If you have any thoughts on optimizing and rephrasing the title, please tell me in your answer then I will try to make the title much clearer.

Suppose we have a list of integers $x_1, x_2,\ldots,x_n$, what we want to find is the smallest integer $y$ such that all the given integers can be found through the process of dividing $y$ by 2 (on the division tree). More specifically, the results of dividing $y$ by 2 are 2 integers: $⌊y/2⌋$ and $⌈y/2⌉$.

Example: for integers 1, 1 and 3, it is easy to prove that the lower bound of y is the sum of them, 5. As for 5, we can get all the integers we want by dividing itself: dividing 5 we get 2 and 3, where 3 is an integer we want; dividing 2 we get 1 and 1, all of which are expected results. Therefore, all the integers we want can be found in the process, 5 is the smallest integer $y$ we want.

Another example: for integers 2, 2 and 6, the lower bound of y is 2+2+6=10, but 10 is not a suitable candidate for y since 10÷2=5<6, it cannot generate 6 in the process. However, if we plus 1, then 11 is the dream y we want. An illustrational graph is shown in the link: picture

Notice that once we get an integer we want on the division tree (i.e. for the 2nd example above, get 6 in a branch of 11), we should accept it as a part of the result, stop dividing it and concentrate on results on the other branch. There also could be some redundant integers generated (i.e. 1 for the 2nd example above), and we just leave them alone.

In all examples above, the smallest integer $y$ is found by trials, not a systematical algorithm. I just cannot come out with an algorithm to find $y$ systematically, and my question is how to find the algorithm.

Improve this question
$\endgroup$
14
  • $\begingroup$ If there are duplicates in x1..x2, like say seven 3s, it means while dividing with 2 either the result or the remainder must contain a total of seven 3s? $\endgroup$
    – Martheen
    Commented Sep 4, 2020 at 1:49
  • $\begingroup$ Martheen what does "the reminder" mean? dividing y we get ⌊y/2⌋ and ⌈y/2⌉, and we will continue to divide these two till all integers we want appear in the tree. If there are seven 3s we want in the list, then 3 should appear 7 times in the division tree (it could be more times, but 7 times at least), and the lower bound of y candidates, therefore, should=7*3+other integers we want. $\endgroup$
    – heklmbbsna
    Commented Sep 4, 2020 at 1:54
  • $\begingroup$ I was talking about the modulo operator (eg, 5%2 = 1), but I was wrong, it's more like the result + the remainder (5%2+5/2=3) $\endgroup$
    – Martheen
    Commented Sep 4, 2020 at 2:00
  • 1
    $\begingroup$ Ah, right, I made the wrong assumption. I just throw 5 and 13 to see if they could ever converge from variations of *2, *2+1 and *2-1, but it doesn't seem that they could $\endgroup$
    – Martheen
    Commented Sep 4, 2020 at 5:08
  • 4
    $\begingroup$ This looks like a competition or possibly homework problem -- if it's from an expired competition, please post the link so that people will feel more comfortable replying. In the meantime, here's a hint: You might be focusing too much on generating the "children" (and further "descendants") of a number; consider thinking about the "parents" (and further "ancestors") of a number instead. $\endgroup$
    – j_random_hacker
    Commented Sep 4, 2020 at 11:50

2 Answers 2

Reset to default
2
$\begingroup$

$x_1=5, x_2=7$ is the smallest example where there is no common ancestor. Any ancestor of $x_1$ is in the range $2 \cdot 2^k + 1 \le z \le 3 \cdot 2^k - 1$, any ancestor of $x_2$ is in the range $3 \cdot 2^k + 1 \le z\le 4 \cdot 2^k - 1$. These are non-overlapping intervals with a gap of one number in between.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The ranges get wider as the ancestor depth $k$ increases -- if $z$ is a $(k-1)$-th ancestor of $x_1$ then we have $2\cdot 2^k - k + 1 \le z \le 2\cdot 2^k + k$ -- but I think you're still right about there being no solution in this case! Nice insight. $\endgroup$
    – j_random_hacker
    Commented Sep 5, 2020 at 14:53
  • $\begingroup$ ... and $2\cdot 2^{k+1} +1>4\cdot 2^k-1$, so these intervals do not overlap. $\endgroup$
    – xskxzr
    Commented Sep 5, 2020 at 15:01
0
$\begingroup$

I think this is one way to do it:

  1. Sort the list in ascending order (actually this can be omitted, but you should drop the 0s)
  2. The first number becomes our candidate
  3. Now we investigate the next number:
    1. Compare the candidate and the next number, the smaller one becomes x the bigger one becomes y
    2. Multiply x by 2 until the next multiplication would exceed y and count the number of multiplications, e.g. x = 2, y = 9 => result r = 8, multiplications m = 2
    3. If r + m >= y then y becomes the candidate, continue with the next number
    4. d = 2 * r - y
    5. do the following calculation d times: y = 2 * y + 1
    6. y becomes the candidate and we continue with the next number

It is based on the idea that if you have a number n = m and calculate x times m = m * 2 + 1, then with m you can get all the numbers in the range from n to n + x.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This seems to be a partial solution only, because it doesn't consider how many times a number must appear in the tree, only if it is possible to build the number. $\endgroup$
    – maraca
    Commented Sep 4, 2020 at 14:52
  • $\begingroup$ What is d? Your algorithm computes d but never uses it. $\endgroup$
    – xskxzr
    Commented Sep 5, 2020 at 1:01
  • $\begingroup$ @xskxzr yes right it should be do the following calculation d times not r times. $\endgroup$
    – maraca
    Commented Sep 7, 2020 at 8:24

Your Answer

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

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