ACM (UVa) : 389


Algorithm:

1. first convert the inputed number into base – 10.

2. then convert the base – 10 number into required base.

Process:

1. take the input as a string.

2. Then we need to make it in a number form. After all we can’t process it until our inputed string contains ‘A’, ‘B’, ‘C’, ‘D’ …

Let, input_string [] is a character array.

Continue ( k = 1 to length of input_string [] ) {
If ( input_string [k] > 47 and input_string [k] < 58 )
digit [k] = input_string [k] – ‘0’;
otherwise
digit [k] = input_string [k] – 55;
}

why 55 ?
numerical sequence : 0 1 2 3 4 5 6 7 8 9 A B C D E F
which means, A = 10, B = 11, C = 12, D = 13, E = 14, F = 15
ASCII value of ‘A’ = 65
so, ‘A’ – 55 = 10
digit [k] will be initiated by 10 if ‘A’ is found.

Similarly, digit [k] will be initiated by 11 if ‘B’ is found.
ASCII value of ‘B’ = 66
so, ‘B’ – 55 = 11

3. now we r gonna to convert it into base – 10

length = character input_string [] – 1
k = length
Continue while ( k > – 1 ) // decrement
Number += ( digit [k] * ( base ^ length – k ) )

4. last and final step : convert this base – 10 number into required base

character output []
k = 0
Continue while ( Number != 0 ) {
temp = Number % required base
if ( temp > 9 )
output [k] = temp + 55
otherwise
output [k] = temp + ‘0’
Number /= required base
}

5. reverse the character array output [] and print it.

Example :
input : ABCD 16 15

input_string [] =

A

B

C

D

Digit [] =

10

11

12

13


length = 3
base = 16
k = 3
base ^ ( length – k ) = base ^ 0 = 16 ^ 0 = 1
digit [k] * base ^ length – k = 13 * 1 = 13
Number = 13

length = 3
base = 16
k = 2
base ^ ( length – k ) = base ^ 1 = 16 ^ 1 = 16
digit [k] * base ^ length – k = 12 * 16 = 192
Number = 13 + 192

length = 3
base = 16
k = 1
base ^ ( length – k ) = base ^ 2 = 16 ^ 2 = 256
digit [k] * base ^ length – k = 11 * 256 = 2816
Number = 13 + 192 + 2816

length = 3
base = 16
k = 0
base ^ ( length – k ) = base ^ 3 = 16 ^ 3 = 4096
digit [k] * base ^ length – k = 10 * 4096 = 40960
Number = 13 + 192 + 2816 + 40960 = 43981

*** ABCD (16) = 43981 (10) ***

43981 (10) = ? (15)

temp = Number % required base
Number (43981) % required base (15) = 1
so, temp = 1
output [] =

1

Number /= required base
Number = 43981 / 15 = 2932

Number (2932) % required base (15) = 1
so, temp = 7
output [] =

1

7

Number /= required base
Number = 2932 / 15 = 195

Number (195) % required base (15) = 1
so, temp = 0
output [] =

1

7

0

Number /= required base
Number = 195 / 15 = 13

Number (13) % required base (15) = 13
so, temp = 13 // as temp > 9 so, temp + 55
temp = 13 + 55 = 68 = ‘D’
output [] =

1

7

0

D

Number /= required base
Number = 13 / 15 = 0 // STOP, as Number is equals to zero

reverse the array

D

0

7

1

Final output : D071

Critical input & output:

The number should be right justified in the 7-digit display

output format

output format

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s