determining large number of two based on digits

Question

I am trying to solve this simple problem. I developed such algorithm, and it seems to work for every possible input I could think of. The following is the exact problem statement on my universiy's online judge.

Task:
You are given two natural N numbers. Compare them by their digits and write the greater one.

Input:
Contains two natural numbers, which modules are not greater than 10¹⁸.

Output:
The greater of two numbers.

Code:

#include <iostream>   // Problem 61, comparing two numbers by their digits.
#include <cmath>
//#include <climits>

using namespace std;

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    long long int n, k; cin >> n >> k;
    long long int x = n, y = k;
    if (n == 0) { cout << k; return 0; } //log(0) undefined
    if (k == 0) { cout << n; return 0; }
    long long int len_n = int(log10(n)) + 1, len_k = int(log10(k)) + 1;
    if (len_n > len_k) { cout << n; }
    else if (len_n < len_k) { cout << k; }
    else {
        long long int num_n, num_k, count_n = 0, count_k = 0;
        for (long long int i = 0; i < len_n; i++) { 
            num_n = n % 10; num_k = k % 10;
            count_n += num_n; count_k += num_k;
            n /= 10; k /= 10;
        }
        if (count_n > count_k) { cout << x; }
        else { cout << y; } 
    }
    return 0;
}

The problem is that it fails test case 4 on the online judge. What am I missing?

Answer 1

You could read the numbers as std::strings and compare them by lexicographical order:

#include <iostream>
#include <string>

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    std::string number1;
    std::string number2; 
    std::cin >> number1 >> number2;
    std::cout << std::max(number1, number2) << '\n';

    return 0;
}

Answer 2

If the problem is indeed to find the greater sum of the digits in two natural numbers, you could make a helper function out of your inner loop, but skip the log10 operation to get the length. Just check if your value is not 0:

inline unsigned sum_digits(unsigned long long x) {
    unsigned result = 0;
    while(x) { // loop for as long as "x" still carries a digit
        result += static_cast<unsigned>(x % 10);
        x /= 10;
    }
    return result;
}

Doing the comparison will then be easy. if(sum_digits(n) < sum_digits(k)) ...

If you want to find the largest of the numbers by comparing them digit by digit, the below approach can work.

#include <iostream>
#include <numeric>
#include <string>

const std::string& comp(const std::string& n, const std::string& k) {
    if(k.size() < n.size())
        return n;
    else if(n.size() < k.size())
        return k;
    else
        for(size_t i = 0; i < n.size(); ++i) {
            if(n[i] < k[i])
                return k;
            else if(k[i] < n[i])
                return n;
        }
    return n; // or k, they are equal
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    unsigned long long n;
    unsigned long long k;
    if(std::cin >> n >> k) {
        std::cout << comp(std::to_string(n), std::to_string(k)) << "\n";
    }
}

If you for any reason can't use std::string, build what you need for the task at hand. Example:

#include <cstdint>
#include <iostream>

// Convert a number to a reversed character array and return the length.
// Only acccept destination arrays exactly fit to store the largest
// possible number for uint64_t (18446744073709551615) which is 20 chars
// plus a zero terminator.
size_t to_reversed_char_array(std::uint64_t x, char (&dest)[21]) {
    char* d_ptr = dest;

    // 0 isn't a natural number, but we'll deal with it anyway
    if(x > 0) {
        // loop for as long as "x" still carries a digit
        for(; x; x /= 10, ++d_ptr)
            // make a char out of the last 10-based digit in "x"
            *d_ptr = static_cast<char>(x % 10 + '0');
    } else { // special case if x == 0
        d_ptr[0] = '0';
        ++d_ptr;
    }
    // null termiator - It's not needed for this to work
    // but if you'd like to print the result out, it is.
    *d_ptr = '\0';

    // Cast from the signed std::ptrdiff_t (the type of the result when subtracting
    // a pointer from another) to size_t, which is safe since we know d_ptr can't
    // be less than dest.
    // The length is also guaranteed to be at least 1
    return static_cast<size_t>(d_ptr - dest);
}

// find the largest number by comparing them digit by digit
std::uint64_t extremely_slow_max(std::uint64_t n, std::uint64_t k) {
    char n_str[21], k_str[21];

    size_t n_len = to_reversed_char_array(n, n_str);
    size_t k_len = to_reversed_char_array(k, k_str);

    if(n_len < k_len)
        return k;
    else if(k_len < n_len)
        return n;

    do {
        // loop from the end of the arrays and compare the numbers digit by digit
        --n_len; // or k_len, they are equal
        if(n_str[n_len] < k_str[n_len])
            return k;
        else if(k_str[n_len] < n_str[n_len])
            return n;
    } while(n_len);

    return n; // or k ... they are equal
}

int main() {
    std::uint64_t n;
    std::uint64_t k;

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    if(std::cin >> n >> k) {
        // std::cout << std::max(n, k) << "\n";
        std::cout << extremely_slow_max(n, k) << "\n";
    }
}