Преобразование числа по основанию 2 в основание 6

Учитывая двоичное целое число N , задача состоит в том, чтобы преобразовать его в основание 6.

Примечание. Количество битов в N не превышает 100.

Примеры:

Input: N = “100111”
Output: 103
Explanation: The given integer (100111)₂ is equivalent to (103)₆.

Input: N = “1111111”
Output: 331

Подход: Данную проблему можно решить, сначала преобразовав данное целое число в десятичное, а затем преобразовав число из десятичного числа в основание 6 , используя подход, обсуждаемый здесь. Обратите внимание, что поскольку значение N может достигать 2 ¹⁰⁰ , для хранения десятичного числа можно использовать 128-битное целое число.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(len(N))
Вспомогательное пространство: O(1)

Другой подход: данная проблема также может быть решена путем сохранения целого числа по основанию 6 вместо десятичного преобразования при преобразовании основания двоичного целого числа в десятичное. Известно, что двоичное число можно преобразовать в десятичное, выполнив следующие действия:

N = “1001”
N can be converted to (N)₁₀ with the equation: (((1*2 + 0) *2 + 0) *2) + 1).

Следовательно, требуются два типа шагов: умножение целого числа на 2, что эквивалентно добавлению целого числа само по себе, и добавление 0 или 1 к целому числу, поскольку (0, 1) ₂ эквивалентно (0, 1) ₆ . Следовательно, сохраняйте строку, представляющую целое число с основанием 6, и на каждом шаге добавляйте целое число к самому себе и добавляйте 0 или 1 соответственно на каждом шаге. Если это можно сделать, используя подход, обсуждаемый здесь.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(len(N) ² )
Вспомогательное пространство: O(len(N))

Обратите внимание, что сложность первого ^{подхода} меньше, чем второго, но первый подход может обрабатывать только двоичные целые числа до 127 бит, а второй подход может обрабатывать и гораздо большие значения.