# Problem Link

**Author:** Jitender Sheora

**Tester:** Mark Mikhno

**Editorialist:** Bhuvnesh Jain

# Difficulty

SIMPLE

# Prerequisites

Pre-computation, Binary-search

# Problem

You are given a number N and you can apply 2 type of operations:

- Add 1 to the number.
- Subtract 1 from the number.

Find the minimum number of operations to be carried such that the resulting number can be represented as 2^x + 2^y, where x and y are non-negative and x != y.

# Explanation

The first thing to note is the optimal answer requires us to apply the only operation of either type. Since the operations negate the effect of each other, we should either only add or subtract from our initial number N.

Suppose, if we have a **sorted list** of all possible final numbers which can be represented in the form, 2^x + 2^y, then we can simply find the number nearest to N. For the smaller number, we can simply apply subtraction operation and for the greater number, we can simply apply the addition operation.

For finding the nearest number greater than or smaller than a given number, we can simply binary search. If you are not familiar with this, you can read topcoder tutorial. There are also inbuilt-functions like “lower_bound” and “upper_bound” in C++ which do your job. (But remember your list should be sorted.)

We can now pre-computate all possible numbers which can be represented in the form 2^x + 2^y. Below is a pseudo-code for it:

```
vals = []
for i in [0, 30]:
for j in [i+1, 30]:
x = (1 << i) + (1 << j)
vals.append(x)
```

Note that the maximum possible exponent of 2 in answer can be ceil(\log{{10}^9}) = 30. This is because, for the minimum operation, we need to find the nearest possible number closest to N.

The size of vals will be (31 * 30) / 2) = 465. Since the size is not large, even iterating through all numbers, instead of applying binary search will pass for the full solution.

Once, you are clear with the above idea, you can see the author or editorialist implementation below for help.

Feel free to share your approach, if it was somewhat different.

# Time Complexity

O({\log}^2{N}) for pre-computation.

O({\log{|vals|}}) per test case.

# Space Complexity

O({\log}^2{N})

# SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.