The Great Battle Conundrum- Who are Alive?

Question

Maximillian is the chief commander of the Great Greek Army and he is leading his forces into a crucial war with Spain.

If all the enemy soldiers stand in a straight line incrementally marked starting from position 1, and a particular soldier at position \$i\$ dies, the soldiers at position \$2i\$ and \$2i+1\$ die as well. This happens in a cascading manner and so, a major part of troops can be killed by just killing one person.

By retrospection, Maximillian realizes that this also means that if the soldier marked \$1\$ (standing at the head of the troops) is killed and then the entire army is defeated. This however is not an easy task as the commander of the Spanish leads the Spanish troops and stands at the head of the troops. When one cascading set of deaths is completed, the remaining troops re-align; filling in the missing gaps and the death rule applies to the new positions.

Let there be \$N\$ soldiers in the enemy's camp marked as \$1,2,3,..., N\$. Maximillian identifies a list of \$K\$ individuals by their marked numbers, who will be executed in a sequential manner. Output the list of soldiers left in the enemy camp in increasing order of their marked values.

---

Input Specification:

input1: N, number of soldiers in the enemy camp

input2: K, number of soldiers to be killed

input3: An array of soldiers numbered between 1 to N who will be killed sequentially in the mentioned order

Output Specification:

Output an array of numbers that belong to soldiers who are alive at the end​ (in increasing order). If all are dead, then output {0}.

---

Test Case 1

input1: 7
input2: 1
input3: {1}

Output: {0}

Explanations:

The soldiers can be represented in the following way:

When Soldier {1} is killed, then {2,3} die.

When {2,3} die, {4,5,6,7} die.

Test Case 2

Example 2:

input1: 7
input2: 2
input3: {2,7}

Output: {1,3,6}

Explanations:

The soldiers can be represented in the following way:

When Soldier - {2} is killed, then {4,5} die.

They do not have any troops at \$2i\$ and \$2i+1\$.

The new representation becomes:

This is code-golf so the shortest code in bytes wins.

---

References:

• https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/comrades-iii/
• https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/practice-problems/algorithm/spartans-leonidas-vs-xerxes-monk/

Answer 1

Jelly, 16 bytes

Ḥ,‘$€F>ÐḟðƬF⁴R¤ḟ

Try it online!

Ḥ,‘$€F>ÐḟðƬF⁴R¤ḟ  Main Link
         ðƬ       While the results don't reach a fixed point
Ḥ                 Double each value (killed soldier)
 , $              Pair            with
    €                  each value
  ‘                                    itself incremented
     F            Flatten the result
       Ðḟ         Filter out (remove) elements that are
      >           Greater than the right argument (the number of soldiers)
           F      Flatten the accumulated list of killed soldiers
               ḟ  Filter; remove the killed soldiers from
            ⁴R¤   [1, 2, ..., N], the list of all soldiers

Answer 2

Python, 125 124 119 bytes

-1 byte thanks to @The Thonnu

def f(n,k,A):*B,=range(n+1);g=lambda d:d<len(B)and g(2*d+1)|g(2*d)|B.pop(d);[g(B.index(x))for x in A];print(B[1:]or[0])

Attempt This Online!

Uses the array representation of a binary tree, then recursively removes the given element and the associated children of that element for each item in A.

Answer 3

Scala, 211 bytes

Modified from @97.100.97.109's answer

Golfed version, Try it online!

def f(n:Int,k:Int,A:List[Int])={var B:List[Int]=(0 to n).toList;def g(d:Int):Unit={if (d<B.length){g(2*d+1);g(2*d);B=B.patch(d,Nil,1);}};A.foreach(x=> g(B.indexOf(x)));println(if(B.length>1)B.tail else List(0))}

Ungolfed verison:

object Main {
  def f(n: Int, k: Int, A: List[Int]): Unit = {
    var B: List[Int] = (0 to n).toList

    def g(d: Int): Unit = {
      if (d < B.length) {
        g(2 * d + 1)
        g(2 * d)
        B = B.patch(d, Nil, 1)
      }
    }

    A.foreach(x => g(B.indexOf(x)))
    println(if (B.length > 1) B.tail else List(0))
  }
  
  def main(args: Array[String]): Unit = {
    f(7, 2, List(2, 7))
  }
}