UVA Problem 575 ( Skew Binary ) Solution

UVA Problem 575 ( Skew Binary ) Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This one is very easy. We need to un-skew or convert to decimal the given input using the given formula.

Inputs are string/ character array because the inputs won’t fit on another data type. Plus it is easier with string.

It is already said after converting our inputs to it will fit in integer data type. Also unsigned can be used here since none of the input, output or calculation result will be zero.

We just need to calculate the formula and print the result.

Important:  Be sure to add or print a new line after each output. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Code Explanation:

Here taking an array of size 32 ( 31+1 for safety  ) will be enough. Code is commented for more look below.


Input:

10120
200000000000000000000000000000
10
1000000000000000000000000000000
11
100
11111000001110000101101102000
0

Output:

44
2147483646
3
2147483647
4
7
1041110737

Code:

/*
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<stdio.h>

/**
 * My custom recursive function to calculate power of two
 */
unsigned int twoPow(unsigned int n){    
    if(n == 0)
        return 1;

    /**
     * this is our recursive counter we need to decrease it otherwise it will go to infinite loop
     */
    n--;    

    /**
     * simply keep multiplying 2 given times to get power of two
     */
    return 2 * twoPow(n); 
}

int main(){
    char s[32];
    unsigned int i,j,sum;   /* here i used unsigned since none of our input or outputs are negative */
    
    while (gets(s)){
        /*
         * check if its 0 then exit, Maybe even deleting the NULL check will work for this problem
         */
        if(s[0] == '0' && s[1] == '\0')    
            return 0;
        
        sum = 0;

        /**
         * get the string length
         */
        for(i = 0; s[i]; ++i);  
        
        for(j = 0; s[j]; ++j)
        /**
         * convert character to integer, then multiply 2 to the power n, then subtract 1 and add to sum
         */
            sum = sum + (s[j] - 48) * (twoPow(i - j) - 1);  
        
        printf("%u\n", sum);
    }
    return 0;
}

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s