План курса / Все задачи / Алгоритмы и структуры данных

Сумма hex чисел

легко

Даны две строки s1 и s2, представляющие собой неотрицательные шестнадцатеричные числа (в нижнем регистре). Необходимо вернуть их сумму также в виде строки — шестнадцатеричного числа (в нижнем регистре).

В решении нельзя использовать втроенные функции для перевода в 16-ричную систему.

Пример 1:

Ввод: s1 = "a", s2 = "5"
Вывод: "f"
Объяснение: 10 + 5 = 15, что в шестнадцатеричной системе равно "f"

Пример 2:

Ввод: s1 = "1a", s2 = "2b"
Вывод: "45"
Объяснение: 26 + 43 = 69, что в шестнадцатеричной системе равно "45"

Ограничения:

len(s1) ≥ 1
len(s2) ≥ 1
s1 и s2 содержат только символы '0'-'9' и 'a'-'f'

public class Solution {
    public static string SumHex(string s1, string s2) {
        List<char> result = new List<char>();
        int p1 = s1.Length - 1;
        int p2 = s2.Length - 1;
        int carry = 0;

        // Пока есть цифры в одном из чисел или есть остаток переноса
        while (p1 >= 0 || p2 >= 0 || carry > 0) {
            if (p1 >= 0) {
                // Добавляем значение цифры из первого числа
                int digit1 = Convert.ToInt32(s1[p1].ToString(), 16);
                carry += digit1;
                p1--;
            }
            if (p2 >= 0) {
                // Добавляем значение цифры из второго числа
                int digit2 = Convert.ToInt32(s2[p2].ToString(), 16);
                carry += digit2;
                p2--;
            }
            // Вычисляем сумму текущих цифр по модулю 16
            int digitSum = carry % 16;
            result.Add((char)(digitSum < 10 ? '0' + digitSum : 'a' + digitSum - 10));
            // Обновляем перенос
            carry /= 16;
        }

        result.Reverse();
        return new string(result.ToArray());
    }
}

#include <string>
#include <vector>

using namespace std;

string sumHex(string& s1, string& s2) {
    vector<char> result;
    int p1 = s1.size() - 1;
    int p2 = s2.size() - 1;
    int carry = 0;

    // Пока есть цифры в одном из чисел или есть остаток переноса
    while (p1 >= 0 || p2 >= 0 || carry > 0) {
        if (p1 >= 0) {
            // Добавляем значение цифры из первого числа
            int digit1 = stoi(s1.substr(p1, 1), nullptr, 16);
            carry += digit1;
            p1--;
        }
        if (p2 >= 0) {
            // Добавляем значение цифры из второго числа
            int digit2 = stoi(s2.substr(p2, 1), nullptr, 16);
            carry += digit2;
            p2--;
        }
        // Вычисляем сумму текущих цифр по модулю 16
        int digitSum = carry % 16;
        result.push_back(digitSum < 10 ? '0' + digitSum : 'a' + digitSum - 10);
        // Обновляем перенос
        carry /= 16;
    }

    reverse(result.begin(), result.end());
    return string(result.begin(), result.end());
}

package main

import (
    "strconv"
)

func sumHex(s1 string, s2 string) string {
    result := []byte{}
    p1 := len(s1) - 1
    p2 := len(s2) - 1
    carry := 0

    // Пока есть цифры в одном из чисел или есть остаток переноса
    for p1 >= 0 || p2 >= 0 || carry > 0 {
        if p1 >= 0 {
            // Добавляем значение цифры из первого числа
            digit1, _ := strconv.ParseInt(string(s1[p1]), 16, 0)
            carry += int(digit1)
            p1--
        }
        if p2 >= 0 {
            // Добавляем значение цифры из второго числа
            digit2, _ := strconv.ParseInt(string(s2[p2]), 16, 0)
            carry += int(digit2)
            p2--
        }
        // Вычисляем сумму текущих цифр по модулю 16
        digitSum := carry % 16
        if digitSum < 10 {
            result = append(result, byte('0'+digitSum))
        } else {
            result = append(result, byte('a'+digitSum-10))
        }
        // Обновляем перенос
        carry /= 16
    }

    // Разворачиваем результат
    for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
        result[i], result[j] = result[j], result[i]
    }
    return string(result)
}

import java.util.*;

public class Solution {
    public String sumHex(String s1, String s2) {
        List<Character> result = new ArrayList<>();
        int p1 = s1.length() - 1;
        int p2 = s2.length() - 1;
        int carry = 0;

        // Пока есть цифры в одном из чисел или есть остаток переноса
        while (p1 >= 0 || p2 >= 0 || carry > 0) {
            if (p1 >= 0) {
                // Добавляем значение цифры из первого числа
                carry += Integer.parseInt(s1.substring(p1, p1 + 1), 16);
                p1--;
            }
            if (p2 >= 0) {
                // Добавляем значение цифры из второго числа
                carry += Integer.parseInt(s2.substring(p2, p2 + 1), 16);
                p2--;
            }
            // Вычисляем сумму текущих цифр по модулю 16
            int digitSum = carry % 16;
            result.add((char) (digitSum < 10 ? '0' + digitSum : 'a' + digitSum - 10));
            // Обновляем перенос
            carry /= 16;
        }

        Collections.reverse(result);
        StringBuilder sb = new StringBuilder();
        for (char ch : result) sb.append(ch);
        return sb.toString();
    }
}

from typing import *

def sum_hex(s1: str, s2: str) -> str:
    result = []
    p1 = len(s1) - 1
    p2 = len(s2) - 1
    carry = 0

    # Пока есть цифры в одном из чисел или есть остаток переноса
    while p1 >= 0 or p2 >= 0 or carry > 0:
        if p1 >= 0:
            # Добавляем значение цифры из первого числа
            digit1 = int(s1[p1], 16)
            carry += digit1
            p1 -= 1
        if p2 >= 0:
            # Добавляем значение цифры из второго числа
            digit2 = int(s2[p2], 16)
            carry += digit2
            p2 -= 1
        # Вычисляем сумму текущих цифр по модулю 16
        digit_sum = carry % 16
        result.append(hex(digit_sum)[2:])
        # Обновляем перенос
        carry = carry // 16

    # Возвращаем результат в правильном порядке
    return ''.join(reversed(result))

/**
 * @param {string} s1
 * @param {string} s2
 * @returns {string}
 */
export function sumHex(s1, s2) {
    const result = [];
    let p1 = s1.length - 1;
    let p2 = s2.length - 1;
    let carry = 0;

    // Пока есть цифры в одном из чисел или есть остаток переноса
    while (p1 >= 0 || p2 >= 0 || carry > 0) {
        if (p1 >= 0) {
            // Добавляем значение цифры из первого числа
            carry += parseInt(s1[p1], 16);
            p1--;
        }
        if (p2 >= 0) {
            // Добавляем значение цифры из второго числа
            carry += parseInt(s2[p2], 16);
            p2--;
        }
        // Вычисляем сумму текущих цифр по модулю 16
        const digitSum = carry % 16;
        result.push(digitSum.toString(16));
        // Обновляем перенос
        carry = Math.floor(carry / 16);
    }

    return result.reverse().join('');
}

Оценка сложности

Время: O(n + m), где n — длина s1, m — длина s2
Память: O(max(n, m)), где n — длина s1, m — длина s2