ALIDEC | Alien Decoder | Editorial

editorial
1

Editorial

Problem Link

Setter: Sidharth Sethi
Tester: Mohit Yadav
Editorial: Tanmay

PROBLEM NAME : Alien Decoder

DIFFICULTY : Easy

PREREQUISITES : None

PROBLEM :
Sidharth has found a way to communicate with the aliens using Binary Digits. He has made an encoder to transfer the number N to aliens. The problem is that the decoder made by aliens is accepting all the Binary Digits in random order. Aliens know about this issue and now they are arranging all the binary digits in such a way that it forms the maximum number out of that.

TASK :
To find out what number aliens might be receiving on their end.

CONSTRAINTS :
1 <= T <= 100
0 <= N <= 2^31

SAMPLE INPUT (1) :
3
0
5
10

SAMPLE OUTPUT (1) :
0
6
12

EXPLANATION :
We must arrange the binary representation of the given number in such a way that all the 1’s appear first, followed by the 0’s, in order to reach the largest feasible number with the binary representation.

To begin, convert the base10 (Decimal Format) values to base2 (Binary Format) and count the 1s and 0s.

Create a number using the above-mentioned approach.

Encode the base2(Binary Format) number to base10(Decimal Format)

EDITORIALIST SOLUTION:

#include <iostream>
#include <string>

using namespace std;

int main()
{
	while(1)
	{
	int n;
	cin >> n;
	int c1 = 0;
	int c0 = 0;
	while(n)
	{
    	if (n & 1)
        	c1++;
    	else
        	c0++;
    	n >>= 1;
	}
    
	string s = "";
	while(c1--)
    		s += '1';
	while(c0--)
    		s += '0';
   	 
	int prd = 1;
	int l = s.length();
	int sum = 0;
    
	while(l--)
	{
    	if (s[l] == '1')
        	sum += prd;
    	prd *= 2;
	}
    
	cout << sum << endl;
    
	}
	return 0;
}

SETTER SOLUTION

#include <iostream>

using namespace std;

int arr[32];
int solve()
{
    int n;
        cin >> n;
    if (n == 0)
          return 0;
     int c0 = 0, c1 = 0;
     unsigned sum = 0;

     while (n)
     {
          if (n & 1)
               c1++;
          else
               c0++;
          n >>= 1;
     }

    for (int i = 0; i < c1; i++)
        sum += arr[c0 + i];
		
	return sum;
}

int main()
{
    arr[0] = 1;
    for (int i = 1; i < 32; ++i)
        arr[i] = arr[i - 1] * 2;
    
    int t;
    cin >> t;
    while(t--)
    {
        cout << solve() << endl;
    }
    
    return 0;
}

OPTIMAL COMPLEXITY:
Time - O(1)
Space- O(1)

2

How about this simple bit trickery?

const int inf = numeric_limits<int>::max();
int clz(int N)
{
    return N ? 32 - __builtin_clz(N) : -inf;
}

int main()
{
    LL tst, x, y, z;
    gl(tst);
    while (tst--)
    {
        gl(x);
        z = 0;
        y = __builtin_popcount(x);
        z = clz(x);
        cout << ((~(~0u << y)) << (z - y)) << endl;
    }
}