Problem: Skew Binary

When a number is expressed in decimal, the k-th digit represents a multiple of pow(10,k). (Digits

are numbered from right to left, where the least significant digit is number 0.) For example,

Image

81307(at decimal)= 8*pow(10,4) + 1*pow(10,3) + 3*pow(10,2) + 0*pow(10,1) + 7*pow(10,0)= 80000 + 1000 + 300 + 0 + 7 = 81307
When a number is expressed in binary, the k-th digit represents a multiple of pow(2,k). For

example,

Image

10011(at binary)= 1*pow(2,4) + 0*pow(2,3) + 0 *pow(2,2) + 1*pow(2,1) + 1*pow(2,0)= 16 + 0 + 0 +2 + 1 = 19

In skew binary, the k-th digit represents a multiple of [pow(2,k+1)-1]. The only possible digits

are 0 and 1, except that the least-significant nonzero digit can be a 2. For example,

Image

10120(skew)= 1*[pow(2,5)-1] + 0*[pow(2,4)-1] + 1*[pow(2,3)-1] + 2*(pow(2,2)-1] + 0*[pow(2,1)-1] = 31 + 0 + 7 + 6 + 0 =44

The first 10 numbers in skew binary are 0, 1, 2, 10, 11, 12, 20, 100, 101, and 102. (Skew
binary is useful in some applications because it is possible to add 1 with at most one carry.
However, this has nothing to do with the current problem.)
Input
The input file contains one or more lines, each of which contains an integer n. If n = 0 it signals
the end of the input, and otherwise n is a nonnegative integer in skew binary.
Output
For each number, output the decimal equivalent. The decimal value of n will be at most pow(2,31)-1 = 2147483647

Sample test(s)
Image

Another picture:

Image

This is my way:

#include <stdio.h>
#include <string.h>
#include <math.h>

/*struct string is used to store input under string form*/
struct __string{
char __S[100];
}__a[1000];
/*struct number is used to convert string to array*/
struct __number{
int __N[100];
}__b[1000];

/*This function is used to convert string to array*/
void _Convert_String_To_Number(char *__s,int *__a,int *__n);
/*This function will convert array to skew binary*/
void _To_Skew_Binary(int *__a,int __n);
/*… just like function pow int math.h*/
unsigned long _Pow(int __a,int __b);

int main(){
/*declare Count to count how many test cases you input*/
int i=0,Count=0;
/*This array contain elements which their value is the length of strings*/
int hold[100];

for(;;){
fflush(stdin);
gets(__a[i].__S);

if(strcmp(__a[i].__S,”0″)==0)
break;
i++;
Count++;
}
/*This loop will convert string to number through the function below*/
for(i=0;i<Count;++i)
_Convert_String_To_Number(__a[i].__S,__b[i].__N,&hold[i]);
/*and this function is used to convert array to skew binary*/
for(i=0;i<Count;++i)
_To_Skew_Binary(__b[i].__N,hold[i]);

}

void _Convert_String_To_Number(char *__s,int *__a,int *__n){
int __length=0,i;
__length=strlen(__s);
for(i=0;i<__length;++i)
__a[i]=__s[i]-‘0’;
/*REturn the length of string*/
*__n=__length;
}

void _To_Skew_Binary(int *__a,int __n){
int i,__k=__n;
unsigned long __Sum=0,__Temp=1;
for(i=0;i<__n;++i){
__Temp=1;
__Temp=__a[i]*(_Pow(2,__k–)-1);
__Sum+=__Temp;
}
/*Print n under the skew binary form*/
printf(“\n%ld”,__Sum);
}

unsigned long _Pow(int __a,int __b){
int i;
unsigned long __Mul=1;
for(i=1;i<=__b;++i)
__Mul*=__a;
return __Mul;
}

Advertisements