Sheokand and Number Solution

Problem

Sheokand is good at mathematics. One day, to test his math skills, Kaali gave him an integer $N$. To impress Kaali, Sheokand has to convert $N$ into an integer $M$ that can be represented in the form $2^x + 2^y$ (where $x$ and $y$ are non-negative integers such that $x \neq y$). In order to do that, he can perform two types of operations:

• add $1$ to $N$
• subtract $1$ from $N$

However, Sheokand is preparing for his exams. Can you help him find the minimum number of operations required to convert $N$ into a valid integer $M$?

Input

• The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
• The first and only line of each testcase contains a single integer $N$.

Output

For each test case, print a single line containing one integer — the minimum required number of operations.

Constraints

• $1 \le T \le 100,000$
• $1 \le N \le 10^9$

Subtasks

Subtask #1 (30 points): $1 \le T \le 1,000$

Subtask #2 (70 points): original constraints

Sample 1:

Input

Output

3
10
22
4

0
2
1

Explanation:

Example case 1: $N=10$ is already in the form $2^x + 2^y$, with $x=3$ and $y=1$.

Example case 2: $N=22$ can be converted into $M=20=2^2+2^4$ or $M=24=2^3+2^4$ in two operations.

Example case 3: $N=4$ can be converted into $M=3=2^0+2^1$ or $M=5=2^0+2^2$ in one operation.

Program :

 /* package codechef; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Codechef

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner sc=new Scanner(System.in);

int t=sc.nextInt();

while(t>0) 

{

    long n=sc.nextInt();

    if(n==1) 

    {

        System.out.println(2);

        --t;

        continue;

    }

    long a=2;

    while(a<n) {

        a*=2;

    }

    if(a==n) 

    {

        System.out.println(1);

    }

    else 

    {

        long ans=Math.min(Math.abs(a+1-n),Math.abs(n-(a/2+1)) );

        long diff=a-a/2,p=2;

        while(p<diff) 

        {

            ans=Math.min(ans,Math.abs(a/2+p-n));

            p=p<<1;

        }

        System.out.println(ans);

    }

    --t;

}

}

}