Let ~C~ and ~C_w~ be the set of pixels colored by draw_circle_filled(~R~) and draw_circle_filled_wrong(~R~), the number of pixels that have different colors in these pictures would be the cardinality (size) of the symmetric difference of ~C~ and ~C_w~, that is:

$$\displaystyle |C \Delta C_w| = |(C \setminus C_w) \cup (C_w \setminus C)|$$

Test Set 1

For test set 1, ~R~ is small enough to build the sets of colored pixels from draw_circle_filled(~R~) and draw_circle_filled_wrong(~R~) with hash set of tuples. By implementing the pseudocode in the problem statement, the time complexity would be ~\mathcal O(R^2)~ to get all colored pixels and ~\mathcal O(R^2)~ to compute the symmetric difference of the two sets.

Test Set 2

The key observation for optimizing the solution is that for any ~R~, every pixel colored by draw_circle_filled_wrong(~R~) is also colored by draw_circle_filled(~R~), that is ~C_w \subseteq C~. Therefore, we can simplify the size of symmetric difference to:

$$\displaystyle \begin{align*} |C \Delta C_w| &= |(C \setminus C_w) \cup(C_w \setminus C) | \\ &= |(C \setminus C_w) \cup \emptyset | \\ &= |C| - |C\cap C_w| \\ &= |C| - |C_w| \end{align*}$$

which means we can count the number of pixels colored by draw_circle_filled(~R~) and draw_circle_filled_wrong(~R~) separately, and the answer would be the difference between these two numbers. The proof of this observation is given at the end of this analysis.

Count pixels colored by draw_circle_filled(~R~)

To get the number of pixels colored by draw_circle_filled(~R~), we need to iterate through all possible values of ~x~ and find ~y_{min}~ and ~y_{max}~ for each ~x~ which satisfy ~\text{round}(\sqrt{x^2 + y^2}) \le R~ for all ~y_{min} \le y \le y_{max}~. A solution for them is ~y_{max} = \text{floor}(\sqrt{R + 0.5}^2 - x^2)~ and ~y_{min} = -y_{max}~. Therefore, we can get the number of colored pixels with a for-loop for the following equation:

$$\displaystyle |C| = \sum_{x=-R}^R \text{floor}(\sqrt{(R + 0.5)^2 - x^2}) \times 2 + 1$$

Time complexity: ~\mathcal O(R)~

Count pixels colored by draw_circle_filled_wrong(~R~)

draw_circle_filled_wrong(~R~) is composed of draw_circle_perimeter(~r~) calls with ~r~ from ~0~ to ~R~. Notice that pixels colored by draw_circle_perimeter(~r_1~) and draw_circle_perimeter(~r_2~) never overlap if ~r_1 \ne r_2~. Based on this observation, we can count the number of pixels colored by each draw_circle_perimeter(~r~) separately and sum them up to get the total number of colored pixels. The proof of this observation is given at the end of this analysis.

Looking into function draw_circle_perimeter(~r~), we can break the colored pixels into 4 quadrants and count them separately. Since the colored pattern is symmetric to both x-axis and y-axis, we just need to count the pixels in Quadrant 1 (Q1), and the total count excluding the origin pixel would be that number times 4, and plus 1 to include the origin pixel.

For ~r \ge 1~, the colored pixels in Q1 are symmetric to the line ~x = y~, and there are exactly ~x_t~ colored pixels between y-axis and ~(x_t, y_t)~, the closest point to line ~x = y~ (above or on the line, ~x_t \ge y_t~). Since ~x = y~ is at ~45^{\circ}~ to the x-axis, the integer ~x_t~ would be either ~\text{ceil}(r/\cos(45^{\circ}))~ or ~\text{floor}(r/\cos(45^{\circ}))~. We can compute the corresponding ~y_t = \text{round}(\sqrt{r^2 - x_t^2})~ and choose the closer one above or on the line ~x = y~. Afterwards, the number of colored pixels in Q1 including x-axis would be ~2 \times x_t + 1~, and minus 1 if ~(x_t, y_t)~ lies on the line ~x = y~ since it is not mirrored in this case.

Time complexity: ~\mathcal O(1)~ for counting pixels colored by draw_circle_perimeter(~r~), and ~\mathcal O(R)~ for all colored pixels.

Proof: ~C_w \subseteq C~

For every positive ~R~, ~r~ and ~x~ such that ~0 \le r \le R~ and ~-r \le x \le r~, we want to prove that the following inequality always satisfies:

$$\displaystyle \begin{align*} & \text{round}(\sqrt{x^2 + \text{round}(\sqrt{r^2 - x^2})^2}) \le r \\ \iff& \sqrt{x^2 + \text{round}(\sqrt{r^2 - x^2})^2} - 0.5 \le r \\ \iff& \sqrt{x^2 + \text{round}(\sqrt{r^2 - x^2})^2} \le r + 0.5 \\ \iff& x^2 + \text{round}(\sqrt{r^2 - x^2})^2 \le r^2 + r + 0.25 \\ \iff& x^2 + (\sqrt{r^2 - x^2} + 0.5)^2 \le r^2 + r + 0.25 \\ \iff& r^2 + \sqrt{r^2 - x^2} + 0.25 \le r^2 + r + 0.25 \\ \end{align*}$$

which always holds since ~\sqrt{r^2 - x^2} \le \sqrt{r^2} = r~ when ~|x| \le r~ and ~r \ge 0~.

Secondly, ~y = \text{round}(\sqrt{r^2 - x^2}) \le \text{round}(\sqrt{r^2}) \le R~. Therefore ~-R \le y \le R~ always holds.

The proof above shows that pixels colored by draw_circle_filled_wrong(~r~) with ~0 \le r \le R~ also satisfy the coloring condition in draw_circle_filled(~R~), which implies ~C_w \subseteq C~.

Proof: draw_circle_perimeter(~r_1~) and draw_circle_perimeter(~r_2~) never overlap

For the first coloring statement in draw_circle_perimeter(~r~), we want to prove that given a fixed ~x~, the inequality ~y_1 = \text{round}(\sqrt{r_1^2 - x^2}) \ne y_2 = \text{round}(\sqrt{r_2^2 - x^2})~ for any pair of integers ~r_1~ and ~r_2~ such that ~r_1 > r_2 \ge 0~ and ~|x| \le r_2~ is always true:

$$\displaystyle \begin{align*} &\mathrel{\phantom{=}} \left|\sqrt{r_1^2 - x^2} - \sqrt{r_2^2 - x^2}\right| \\ &= \sqrt{r_1^2 - x^2} - \sqrt{r_2^2 - x^2} &\; r_1 > r_2 \\ &\ge \sqrt{r_1^2 - x^2} - \sqrt{(r_1 - 1)^2 - x^2} &\; r_1\text{ and }r_2\text{ are integers} \\ &\ge \left(\sqrt{r_1^2} - \sqrt{x^2}\right) - \left(\sqrt{(r_1 - 1)^2} - \sqrt{x^2}\right) &\; \text{for any }|x| \le r_1 - 1 \\ &= r_1 - x - (r_1 - 1) + x \\ &= 1 \end{align*}$$

Based on the proof above, we can further get:

$$\displaystyle \begin{align*} & \text{round}(\sqrt{r_1^2 - x^2}) - \text{round}(\sqrt{r_2^2 - x^2}) \\ \ge\;& \text{round}(\sqrt{r_1^2 - x^2}) - \text{round}(\sqrt{(r_1 - 1)^2 - x^2}) \\ \ge\;& \text{round}(\sqrt{r_1^2 - x^2}) - \text{round}(\sqrt{r_1^2 - x^2} - 1) \\ \ge\;& 1 \end{align*}$$

Therefore ~y_1 \ne y_2~ always holds for all ~r_1 > r_2 \ge 0~ given a fixed ~x~ such that ~|x| \le r_2~. For the cases that ~r_2 < |x| \le r_1~, the pixels will never satisfy the coloring condition in draw_circle_perimeter(~r_2~).

We can further extend the proof above for the 2nd, 3rd, and 4th coloring statement in draw_circle_perimeter(~r~) and prove that pixels colored by draw_circle_perimeter(~r_1~) and draw_circle_perimeter(~r_2~) never overlap.