find-nth-smallest-integer-with-k-one-bits

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given two positive integers <code>n</code> and <code>k</code>.

Return an integer denoting the <code>nth</code> smallest positive integer that has exactly <code>k</code> ones in its binary representation. It is guaranteed that the answer is strictly less than <code>250</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: n = 4, k = 2

Output: 9

Explanation:

The 4 smallest positive integers that have exactly <code>k = 2</code> ones in their binary representations are:

<ul>
	<li><code>3 = 112</code></li>
	<li><code>5 = 1012</code></li>
	<li><code>6 = 1102</code></li>
	<li><code>9 = 10012</code></li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: n = 3, k = 1

Output: 4

Explanation:

The 3 smallest positive integers that have exactly <code>k = 1</code> one in their binary representations are:

<ul>
	<li><code>1 = 12</code></li>
	<li><code>2 = 102</code></li>
	<li><code>4 = 1002</code></li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 250</code></li>
	<li><code>1 &lt;= k &lt;= 50</code></li>
	<li>The answer is strictly less than <code>250</code>.</li>
</ul>