---{"category_name":"easy","problem_code":"ODDBITS","problem_name":"Odd bits","problemComponents":{"constraints":"- $1 \\leq T \\leq 10^3$\n- $1 \\leq N \\leq 10^9$\n","constraintsState":true,"subtasks":"","subtasksState":false,"inputFormat":"- First line will contain $T$, number of testcases. Then the testcases follow.\n- Each testcase contains of a single line of input, an integer $N$.\n","inputFormatState":true,"outputFormat":"For each testcase, output in a single line the minimum possible value of $K$.\n","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"3\n2\n6\n100","output":"2\n5\n57","explanation":" - In the first test case, binary representations of $1$ and $2$ are **1**, **1**0. Sum of bits present on odd positions in the binary representation of $1$ and $2$ = $1 + 1$ = $2$.\n - In the second test case, the binary representations of integers from $1$ to $5$ are **1**, **1**0, \n **1**1, **1**0**0**, **1**0**1** respectively. So the sum of bits present on odd positions in binary \n representation of integers from $1$ to $5$ are $1, 1, 1, 1, 2$ respectively which makes a total of $6$.","isDeleted":false}}},"video_editorial_url":"","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"soumyadeep_21","problem_tester":"","date_added":"9-07-2021","tags":{"0":"binary","1":"digit","2":"easy","3":"soumyadeep_21","4":"start7","5":"vichitr"},"problem_difficulty_level":"Easy-Medium","best_tag":"Binary Search","editorial_url":"https://discuss.codechef.com/problems/ODDBITS","time":{"view_start_date":1627219800,"submit_start_date":1627219800,"visible_start_date":1627219800,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=ODDBITS","is_proctored":false,"visitedContests":{},"layout":"problem"}---### Read problem statements in [Russian](https://www.codechef.com/download/translated/START7/russian/ODDBITS.pdf) and [Mandarin Chinese](https://www.codechef.com/download/translated/START7/mandarin/ODDBITS.pdf).Find the minimum integer $K$ such that sum of bits present on odd positions in binary representation of all integers from $1$ to $K$ is greater than or equal to $N$.The bits are enumerated from left to right starting from the leftmost set bit i.e. the most significant bit. For example, binary representation of $77$ is **1**0**0**1**1**0**1**. Bits present on $1^{st}$, $3^{rd}$, $5^{th}$ and $7^{th}$ positions in the binary representation are $1, 0, 1, 1$ respectively. So sum of bits present on odd positions in binary representation of $77$ is $1 + 0 + 1 + 1 = 3$.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>