Tidy Bits - Ad-hoc Problems - Solution to Toph.co Online Judge Problem

Tidy Bits

Limits 1s, 512 MB

Read an integer variable, and determine the smallest positive integer that has the same number of $\texttt{1}$s in its bit representation as the number you read.

The following numbers all have the same number of $\texttt{1}$s in their bit representation: 7 ($\texttt{111}$), 13 ($\texttt{1101}$), 37 ($\texttt{100101}$), etc. And among all such positive integers, 7 is the smallest number that has 3 $\texttt{1}$s in its bit representation.

Input

The input will contain an integer $A$ ($0 \le A < 1000000$).

Output

Print the smallest positive integer that has the same number of $\texttt{1}$s in its bit representation as $A$.

Sample

Input	Output
37	7

Solution:

#include<stdio.h> int main() { int n,s,temp,count=0,c=0,i,p,result; scanf("%d", &n); s=n; while(n!=0) { temp=n%2; if(temp==1) count++; n=n/2; } for(i=s-1;i>=1;i--) { p=i; while(p!=0) { temp=p%2; if(temp==1) c++; p=p/2; } if(c==count) result=i; c=0; } printf("%d",result); }