Problem Specification

Given a set of positive hexadecimal integers, transform each into its octal equivalent. The input provides a count n (1 ≤ n ≤ 10), followed by n strings composed of digits 0-9 and uppercase letters A-F. Each string can be up to 100,000 characters long. Neither the input nor the output should contain leading zeros.

Conversion Strategy

Direct mathematical conversion for strings of this length is inefficient and prone to overflow. The optimal approach leverages intermediate binary representation:

1. Translate each hexadecimal character into its 4-bit binary equivalent.
2. Pad the resulting binary string with leading zeros until its length is a multiple of 3.
3. Segment the binary string into 3-bit groups and map each group to its corresponding octal digit.
4. Strip any leading zeros from the final octal output.

Hexadecimal to Octal Implementation

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
    unordered_map<char, string> hexToBin = {
        {'0', "0000"}, {'1', "0001"}, {'2', "0010"}, {'3', "0011"},
        {'4', "0100"}, {'5', "0101"}, {'6', "0110"}, {'7', "0111"},
        {'8', "1000"}, {'9', "1001"}, {'A', "1010"}, {'B', "1011"},
        {'C', "1100"}, {'D', "1101"}, {'E', "1110"}, {'F', "1111"}
    };

    unordered_map<string, char> binToOct = {
        {"000", '0'}, {"001", '1'}, {"010", '2'}, {"011", '3'},
        {"100", '4'}, {"101", '5'}, {"110", '6'}, {"111", '7'}
    };

    int count;
    cin >> count;
    while (count--) {
        string hexInput, binaryStr = "", octalStr = "";
        cin >> hexInput;

        for (char c : hexInput) {
            binaryStr += hexToBin[c];
        }

        int padding = (3 - binaryStr.length() % 3) % 3;
        binaryStr = string(padding, '0') + binaryStr;

        for (size_t i = 0; i < binaryStr.length(); i += 3) {
            string segment = binaryStr.substr(i, 3);
            octalStr += binToOct[segment];
        }

        size_t firstNonZero = octalStr.find_first_not_of('0');
        if (firstNonZero != string::npos) {
            cout << octalStr.substr(firstNonZero) << endl;
        } else {
            cout << "0" << endl;
        }
    }
    return 0;
}

Supplementary: Hexadecimal to Decimal

The same intermediate binary approach can be adapted to compute the decimal value. Note that standard integer types will overflow with extremely long strings, so this is primarily suited for shorter inputs.

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
    unordered_map<char, string> hexToBin = {
        {'0', "0000"}, {'1', "0001"}, {'2', "0010"}, {'3', "0011"},
        {'4', "0100"}, {'5', "0101"}, {'6', "0110"}, {'7', "0111"},
        {'8', "1000"}, {'9', "1001"}, {'A', "1010"}, {'B', "1011"},
        {'C', "1100"}, {'D', "1101"}, {'E', "1110"}, {'F', "1111"}
    };

    string hexInput, binaryStr = "";
    cin >> hexInput;

    for (char c : hexInput) {
        binaryStr += hexToBin[c];
    }

    unsigned long long decimalValue = 0;
    for (char bit : binaryStr) {
        decimalValue = decimalValue * 2 + (bit - '0');
    }

    cout << decimalValue << endl;
    return 0;
}