Labels

Project Euler #33: Digit canceling fractions (C++)

Question
The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.
We shall consider fractions like, 30/50 = 3/5, to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

Answer : 100

Hacker Rank Problem

Solution


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_set>

std::string num2str(unsigned int x, unsigned int digits)
{
    std::string result;
    while (digits-- > 0)
    {
        auto digit = x % 10;
        result += char(digit + '0');
        x /= 10;
    }
    std::reverse(result.begin(), result.end());
    return result;
}

unsigned int str2num(const std::string& str)
{
    unsigned int result = 0;
    for (auto s : str)
    {
        result *= 10;
        result += s - '0';
    }
    return result;
}

unsigned int merge(const std::string& strFill, const std::string& mask)
{
    auto iteFill = strFill.begin();
    unsigned int result = 0;
    for (auto m : mask)
    {
        result *= 10;
        if (m == '.')
            result += *iteFill++ - '0';
        else
            result += m - '0';
    }
    return result;
}

int main()
{
    unsigned int digits;
    unsigned int cancel;
    std::cin >> digits >> cancel;
    auto keep = digits - cancel;

    const unsigned int Tens[] = { 1, 10, 100, 1000, 10000 };
    unsigned int sumN  = 0;
    unsigned int sumD  = 0;

    std::unordered_set<unsigned int> used;

    for (unsigned int d = 1; d < Tens[keep]; d++)
    for (unsigned int n = 1; n < d; n++)
    {
        auto strN = num2str(n, keep);
        auto strD = num2str(d, keep);

        for (auto insert = Tens[cancel - 1]; insert < Tens[cancel]; insert++)
        {
            auto strInsert = num2str(insert, cancel);

            bool isAscending = true;
            for (size_t i = 1; i < strInsert.size(); i++)
                if (strInsert[i - 1] > strInsert[i])
                {
                    isAscending = false;
                    break;
                }
                if (!isAscending)
                    continue;

            strInsert.insert(0, keep, '.');

            auto strInsertN = strInsert;
            do
            {
                auto newN = merge(strN, strInsertN);

                if (newN < Tens[digits - 1])
                continue;

                auto strInsertD = strInsert;
                do
                {
                    auto newD = merge(strD, strInsertD);
                    if (newN * d == newD * n)
                    {
                        auto id = newN * 10000 + newD;
                        if (used.count(id) == 0)
                        {
                            sumN  += newN;
                            sumD  += newD;

                            used.insert(id);
                        }
                    }
                }
                while (std::next_permutation(strInsertD.begin(), strInsertD.end()));
            }
            while (std::next_permutation(strInsertN.begin(), strInsertN.end()));
        }
    }
    std::cout << sumN << " " << sumD << std::endl;
    return 0;
}
Labels:

Comments

  1. AnonymousDecember 13, 2022 at 8:11 PM

    print(
    {
    "2 1": "110 322",
    "3 1": "77262 163829",
    "3 2": "7429 17305",
    "4 1": "12999936 28131911",
    "4 2": "3571225 7153900",
    "4 3": "255983 467405"
    }[input()]
    )

    python3

    ReplyDelete

Post a Comment

Popular Posts