DEV Community

loading...

UVA 11933 - Splitting Numbers

Nithin SJ
An Aspiring Competitive Programmer, Self taught Full Stack Developer. Looking to give back to the community.
・2 min read

Problem statement
We define the operation of splitting a binary number n into two numbers a(n), b(n) as follows. Let 0 ≤ i1 < i2 < . . . < ik be the indices of the bits (with the least significant bit having index 0) in n that are 1. Then the indices of the bits of a(n) that are 1 are i1, i3, i5, . . . and the indices of the bits of b(n) that are 1 are i2, i4, i6, . . . For example, if n is 110110101 in binary then, again in binary, we have a = 010010001 and b = 100100100.
Input
Each test case consists of a single integer n between 1 and 231 − 1 written in standard decimal (base 10) format on a single line. Input is terminated by a line containing ‘0’ which should not be processed.
Output
The output for each test case consists of a single line, containing the integers a(n) and b(n) separated by a single space. Both a(n) and b(n) should be written in decimal format.
Sample Input
6
7
13
0
Sample Output
2 4
5 2
9 4

Observation
Here, for every time ith bit is set, set ith bit of a and b alternatively.

Code

/*
Author : humanbeeng
*/
#include <bits/stdc++.h>
using namespace std;
#define fo(i, n) for (int i = 0; i < n; i++)
#define pb(num) push_back(num)
#define ppb pop_back()
#define all(arr) arr.begin(), arr.end()
#define pi(arr)                                            \
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) \
    cout << arr[i] << ' '
#define imn INT_MIN
#define imx INT_MAX
#define mod 1000000007
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<ii> vii;
typedef vector<char> vc;
typedef unsigned long long ull;
typedef set<string, int> ssi;
typedef set<int> si;
typedef set<string> ss;

void setio(string s) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

int main() {
    //setio("");
    int num;
    while (cin >> num && num != 0) {
        bitset<32> a(0);
        bitset<32> b(0);
        bitset<32> n(num);
        int sw = 0;
        int i = 0;
        while(i<32){
            if(n.test(i) && sw == 0){
                a.set(i);
                sw = 1;
            }else if(n.test(i) && sw == 1){
                b.set(i);
                sw = 0;
            }
            i++;
        }
        int aa = a.to_ulong();
        int bb = b.to_ulong();
        cout << aa << " " << bb << endl;


    }

    return 0;
}
Enter fullscreen mode Exit fullscreen mode

Discussion (0)

Forem Open with the Forem app