Maximizing cos(x) + cos(y) + cos(z)

It's been a while since my last blog. Since it's getting closer to IEEEXtreme 12.0 I thought of sharing an algorithmic challenge I tried in one of the past competitive programming contests. I had a thought of penning down some insight into this challenge ever since I solved this. For whatever the reason (maybe for the reason I managed to solve this!) this challenge seems to be quite exciting.

First of all, I must say that I am not the author of this challenge and in fact, I can't remember the place I encountered this challenge. (If you happen to know the original author please let me know so that I could give credit to him here) I even created a Hackerrank problem using this. (You can have a try, link)

First, let's take a look at the task.

Find the maximum value of $\cos{x} + \cos{y} + \cos{z}$ given that $x + y + z = n$ where $x, y, z, n$ are positive integers. The input constraint was $3 \leq n \leq 3 \times 10^6$

The task description is clear and there is no ambiguity. Now that the task is in order let's see how to solve this. The typical first approach one would think is brute force. It is evident that $z = n - (x + y)$ hence if $x$ and $y$ are fixed $z$ will become a constant. In such a case, we need to try out all the possible values for $x$ and $y$ and keep track of the maximum value for the summations. However, the time complexity of that approach will become $\mathcal{O}(n^2)$ making it less efficient. We can reduce the time complexity much further. That is when mathematics comes into rescue! (as always)

Think about the task a bit more. You might remember from your high school some equations to some up two $\cos{}$ terms.

\[\cos A + \cos B = 2 \cos \dfrac{A+B}{2} \cos \dfrac{A-B}{2}\]

Let's use this equation. Now the function becomes,

\[2 \cos \dfrac{x+y}{2} \cos \dfrac{x-y}{2} + \cos(n-(x+y))\]

Now comes the most elegant part of this problem! Now you can see the there is only $x+y$ and $x-y$ are left as values depending on variables. Let's see why seeing the problem in this new perspective is crucial. Think when $x+y$ is an even number. In that scenario, for any $x+y$ even value we can set $x=y=\frac{(x+y)}{2}$. That means we can find values for $x$ and $y$ where $x=y$. Now that means we can set $\cos\frac{x-y}{2} = \cos(0) = 1$ which is the maximum value for any cosine. Now we can iterate through $x+y$ values (for even case) and compute the maximum value possible for $2 \cos \dfrac{x+y}{2} + \cos(n-(x+y))$. Now the case is solved for even $x+y$ sum.

Let's see how to calculate the maximum for odd $x+y$ values. The tabe below shows how values of $x+y$ and $x-y$ vary. (Here $abs(x-y)$ is considered because $\cos(-x) = \cos(x)$.)

It is apparent from the table how the values for $x-y$ vary with values for $x+y$. One key observation is that $x+y-2$ is always get added to the possible values for $x-y$ while all the other possible values remaining unchanged. That is one of the decisive observations! That means you can keep track of what is the maximum value for $\cos\frac{x-y}{2}$ while iterating through. Thus making no need to iterate through possible values for $x-y$. With that observation, we can find the maximum value for the function for odd $x-y$ values as well.

Yay! That is the solution. This works in $\mathcal{O}(n)$ time. The code for the above problem is shown below.

As far as I remember I spent a couple of hours trying to solve this problem until I finally managed to solve this. I tried various different approaches and ultimately managed to come up with this solution. (I was just writing stuff on the paper and this idea randomly came into my mind) This marks the end of this blog. I hope it was interesting. If there's any clarifications/comment please let me know in the comments. Thank you for reading.