3
$\begingroup$

I have some $n$ numbers which are powers of $2$, say $a_1,a_2,a_3,\ldots,a_n$ which are not necessarily all distinct. I have option to give them any sign. I have to find if I can make their sum after that equal to num.

I have following algorithm which I am sure will work, by a lot of arguments and verification, but I am not able to prove it:

  1. We sort the array.
  2. Initialize another variable temp to $0$.
  3. We traverse from highest element to lowest element.
  4. If temp>num then subtract $a_i$, else add $a_i$. If in the end temp=num then it's possible to assign signs such that we can make num out the array, otherwise it is not possible.

How to prove that the algorithm works?

Improve this question
$\endgroup$
4
  • $\begingroup$ If you are sure it works, you just write down your "lot of arguments and verification". But I would look for a counterexample instead. $\endgroup$
    – Hendrik Jan
    Dec 24, 2020 at 17:59
  • $\begingroup$ @HendrikJan Verification i did by taking examples and it worked for all . The arguments i made while verifying could not used for proving . But i can assure you that by finding counter example you will waste your time because i am confident it's correct (I wrote a program for verifying for random inputs and it gave same answer as brute force). $\endgroup$
    – TheReal__Mike
    Dec 24, 2020 at 18:26
  • $\begingroup$ Say the given powers of 2 were {2,4,8,16} and num=26 .let temp = 0 , since temp<26 , do temp+=16 , since 16<26 , do temp+=8 i.e temp = 24 , since 24<26 , do temp+=4 , since 28>26 , do temp-=2 , thus in end temp=26 , hence 26 can be made from the array . Note that this is an example and all elements of array are not necessarily distinct . $\endgroup$
    – TheReal__Mike
    Dec 24, 2020 at 18:28
  • $\begingroup$ Ah, sorry. I overlooked the condition that all numbers are powers of two. That is a huge difference. I will start thinking again. Thanks for the example. $\endgroup$
    – Hendrik Jan
    Dec 24, 2020 at 19:11

1 Answer 1

Reset to default
2
$\begingroup$

You can prove the algorithm using induction. In order to prove by induction, your main statement would be: Let $s_n$ be the (correct) sign of $a_n$ (if it exists), then the algorithm trying to find $s^*_1,\dots,s^*_{n-1}$ such $\sum_{i=1}^{n-1} s^*_ia_i=num-s_na_n$ is correct (by induction assumption). Then, we only need to show that the algorithm chooses $s^*_n=s_n$ and then we would get $\sum_{i=1}^n s^*_ia_i=num-s_na_n+s^*_na_n=num$ as required.

Now the tricky part comes: how can we prove that the $s^*_n$ the algorithm chooses is indeed correct? We want to split this part into two cases:

  • $num\ge0$, and assume towards contradiction $s_n\neq 1$, i.e only $s_n=-1$ gives a valid solution (there may be multiple solutions, so beware of saying there is only one such $s_n$). Then we need to have $\sum_{i=1}^{n-1}s_ia_i = num+a_n$. Since we are dealing with only powers of $2$, and $a_n$ is the highest value, then there must be some values whose sum (when summed with the appropriate sign) is precisely $a_n$ (and this is because $a_n$ is also a power of 2, if you want a complete proof to this statement, think about the numbers as binary numbers with only one "1" in them and the rest are "0"s), now we can "flip" the sign of those values, and we would get $\sum_{i=1}^{n-1}=num-a_n$ (since their sum is $a_n$, the effect of flipping their sign is like subtructing $2a_n$) and then by choosing $s_n=+1$ we get $\sum_{i=1}^n s_ia_i=num$, in contradiction to our assumption.
  • $num < 0$, we get that $s^*_n=-1$, and by flipping all of the signs as well as the sign of $num$ we get $s^*_n=1$ for $num>0$, and notice this is the same as the first case.
Improve this answer
$\endgroup$
3
  • $\begingroup$ This solution doesn't takes "temp" into account $\endgroup$
    – TheReal__Mike
    Dec 24, 2020 at 20:31
  • 1
    $\begingroup$ it does, think about it in a different way: at the k'th step, $temp=\sum_{i=n-k+1}^n s^*_ia_i$, and we want to find $s^*_1,\dots,s^*_{n-k}$ such that $\sum_{i=1}^n s^*_ia_i=num$. This is equivalent to asking if we can find such $s^*_i$'s with $\sum_{i=1}^{n-k} s^*_ia_i = num - temp$, meaning that $num-temp>0\implies num > temp$. This means that thinking of updating $num$ itself instead of $temp$ is equivalent, and the "if" statement checks whether its greater than 0 rather than checking $num > temp$. $\endgroup$
    – nir shahar
    Dec 24, 2020 at 20:37
  • 1
    $\begingroup$ I get you , basically sign of right hand side tells if $temp>num$ or $temp<=num$. $\endgroup$
    – TheReal__Mike
    Dec 24, 2020 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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