1. Definition
Here is the definition of heavy number, given a integer not less than zero. If the average of all its digits is more than 7, then it is called heavy number. For instance,
- 999: (9+9+9)/3 = 9 > 7, it is a heavy number
- 777: (7+7+7)/3 = 7 not > 7, it is not a heavy number
The exercise is to calculate how many heavy numbers given a range.
2. Analysis
I believe this is sort of similar programming exercise as I introduced in my other blog entry, Dynamic programming - Sum K of N dices with S sides. Here is the illustration,
- S sides: 10 sides, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9;
Except the first digit can only have 9 sides, 1, 2, 3, 4, 5, 6, 7, 8, 9
- N dices: number of digits, 999 - 3 digits/dices, 12345 - 5 digits/dices
- Sum K: for 1 digit (0 ~ 9), K = 8, 9
for 2 digits (10 ~ 99), K = 15, 16, 17, 18
for 3 digits (100 ~ 99), K = 22, 23, 24, 25, 26, 27
......
for n digits (pow(10, n-1) ~ pow(10, n) - 1), K = 7*n+1, ......, 9*n
3. Algorithm
Pseudo-code,
- Calculate how many digits the given range comes across
- Sum all them heavy numbers of the full range given i digits
- Sum the heavy numbers of upper range
- Minus the heavy numbers of lower range
Here is an example: given a range [80, 234567891]
- digits across: 2, 3, 4, 5, 6, 7, 8, 9
- Sum all the heavy number of given digits of 2, 3, 4, 5, 6, 7, 8
- Sum all the heavy number of upper range [100000000, 234567891]
- Minus the heavy numbers of lower range [10, 80), not including 80
The last two steps prove to be very difficult. It is implemented in GetNumOfHeavyNumbersGivenListOfNum().
The idea is to convert to the sub-problems of calculating the heavy number of given i digits. Here is how to do with [100000000, 234567891]
- [234567890, 234567891]
- [234567800, 234567889]
* Known sum = 2 + 3 + 4 + 5 + 6 + 7 + 8 = (2+8) / 2 * 7 = 35
* Heavy number requirement: 9*7+1 = 64
* Sub-problem: K >= 64 - 35 = 29
* N dices: 2
* S sides: 1st dice [0, 8], 2nd dice [0, 9]
- [234567000, 234567799]
* Known sum = 2 + 3 + 4 + 5 + 6 + 7 = (2+7) / 2 * 6 = 27
* Heavy number requirement: 9*7+1 = 64
* Sub-problem: K >= 64 - 27 = 37
* N dices: 3
* S sides: 1st dice [0, 7], 2nd and 3rd dice [0, 9]
......
- [100000000, 199999999]
* Known sum = 1
* Heavy number requirement: 9*7+1 = 64
* Sub-problem: K >= 64 - 1 = 63
* N dices: 8
* S sides: all [0, 9]
Here come the code:
//********************************************************************************
// HeavyNumberImpPolynomial.h
#ifndef HEAVY_NUMBER_IMP_POLYNOMIAL_H
#define HEAVY_NUMBER_IMP_POLYNOMIAL_H
#pragma once
#include <unordered_map>
class HeavyNumberImpPolynomial
{
public:
HeavyNumberImpPolynomial();
~HeavyNumberImpPolynomial();
virtual size_t GetNumOfHeavyNumbersAgainstNdigits(long nDigits);
size_t GetNumOfHeavyNumbersAgainstRange(size_t start, size_t end);
const static size_t AVERAGE_VALUE_OF_HEAVY_NUM = 7;
private:
struct HV_KEY{
long nDigits;
long SUM;
bool operator()(const HV_KEY& right) const {
return right.nDigits == nDigits && right.SUM == SUM;
}
};
struct HV_KEY_HASH{
size_t operator()(const HV_KEY& key) const {
return std::hash<long>()(key.nDigits) ^std::hash<long>()(key.SUM);
}
bool operator()(const HV_KEY& k1, const HV_KEY& k2) const {
return k1.operator()(k2);
}
};
typedef std::unordered_map<HV_KEY, size_t, HV_KEY_HASH, HV_KEY_HASH> HV_CACHE;
size_t CountCombinatonsGivenSumOfNdigits(long nDigits, long nSides,
long sum, HV_CACHE& hvCache);
void GetDigitsOfNumber(size_t num, std::vector<unsigned int>& digits);
size_t GetNumOfHeavyNumbersGivenListOfNum(const std::vector<unsigned int>& digits);
size_t GetLeastHeavyNumGivenNdigits(size_t n);
};
#endif
#include "stdafx.h"
#include "HeavyNumberImpPolynomial.h"
#include <assert.h>
#include <numeric>
HeavyNumberImpPolynomial::HeavyNumberImpPolynomial()
{
}
HeavyNumberImpPolynomial::~HeavyNumberImpPolynomial()
{
}
size_t HeavyNumberImpPolynomial::GetNumOfHeavyNumbersAgainstRange(size_t start, size_t end)
{
if (start > end) {
return 0;
}
std::vector<unsigned int> digitsOfStart;
GetDigitsOfNumber(start, digitsOfStart);
std::vector<unsigned int> digitsOfEnd;
GetDigitsOfNumber(end, digitsOfEnd);
size_t count = std::accumulate(digitsOfEnd.begin(), digitsOfEnd.end(), 0.0) /
digitsOfEnd.size() > AVERAGE_VALUE_OF_HEAVY_NUM ? 1 : 0;
for (size_t digit = digitsOfStart.size(); digit < digitsOfEnd.size(); ++digit) {
count += GetNumOfHeavyNumbersAgainstNdigits(digit);
}
if (end >= GetLeastHeavyNumGivenNdigits(digitsOfEnd.size())) {
count += GetNumOfHeavyNumbersGivenListOfNum(digitsOfEnd);
}
if (start >= GetLeastHeavyNumGivenNdigits(digitsOfStart.size())) {
count -= GetNumOfHeavyNumbersGivenListOfNum(digitsOfStart);
}
return count;
}
size_t HeavyNumberImpPolynomial::GetNumOfHeavyNumbersAgainstNdigits(long nDigits)
{
if (nDigits < 0) {
return 0;
}
const static size_t PRE_COMPUTED_NUM_OF_HV[9] = { 0, 2, 10, 56,
330, 2001, 12313, 76470, 478302 };
if (nDigits <= 8) {
return PRE_COMPUTED_NUM_OF_HV[nDigits];
}
size_t numOfHN = 0;
HV_CACHE hvCache;
const size_t heaviness = nDigits * AVERAGE_VALUE_OF_HEAVY_NUM + 1;
const long nSides = 9;
for (size_t topDigits = 1; topDigits <= nSides; ++topDigits) {
numOfHN += CountCombinatonsGivenSumOfNdigits(nDigits - 1, nSides,
heaviness - topDigits, hvCache);
}
return numOfHN;
}
size_t HeavyNumberImpPolynomial::CountCombinatonsGivenSumOfNdigits(
long nDigits,
long nSides,
long sum,
HV_CACHE& hvCache)
{
if (sum > nSides * nDigits) {
return 0;
}
if (sum <= 0 && nDigits == 0) {
return 1;
}
const HV_KEY key{ nDigits, sum };
HV_CACHE::const_iterator cachedIter = hvCache.find(key);
if (cachedIter != hvCache.end()) {
return cachedIter->second;
}
size_t count = 0;
for (size_t val = 0; val <= nSides; ++val) {
count += CountCombinatonsGivenSumOfNdigits(nDigits - 1,
nSides, sum - val, hvCache);
}
hvCache.insert(std::make_pair(key, count));
return count;
}
void HeavyNumberImpPolynomial::GetDigitsOfNumber(
size_t num,
std::vector<unsigned int>& digits)
{
digits.clear();
if (num == 0) {
digits.push_back(0);
return;
}
while (num) {
digits.push_back(num % 10);
num /= 10;
}
return;
}
size_t HeavyNumberImpPolynomial::GetNumOfHeavyNumbersGivenListOfNum(
const std::vector<unsigned int>& digits)
{
if (digits.empty()) {
return 0;
}
long numOfDigits = digits.size();
assert(digits[numOfDigits - 1] > 0);
long sum = numOfDigits * AVERAGE_VALUE_OF_HEAVY_NUM + 1;
size_t start;
size_t count = 0;
HV_CACHE hvCache;
const long nSides = 9;
while (numOfDigits) {
start = numOfDigits == digits.size() ? 1 : 0;
for (size_t digit = start; digit < digits[numOfDigits - 1]; ++digit) {
count += CountCombinatonsGivenSumOfNdigits(numOfDigits - 1,
nSides, sum - digit, hvCache);
}
sum -= digits[numOfDigits - 1];
--numOfDigits;
}
return count;
}
/*
* n = 1, return 8
* n = 2, return 69
* n = 3, return 499
* n = 4, return 2999
* n = 5, return 18999
* n = 6, return 169999
* Start to broke when n is too big for Win32
* because overflow will happen (n < 11)
*
*/
size_t HeavyNumberImpPolynomial::GetLeastHeavyNumGivenNdigits(size_t n)
{
const size_t PRE_COMPUTED_LEAST_HN[] = { 8,
69,
499,
2999,
18999,
169999,
1499999,
12999999,
109999999,
1079999999 };
if (n == 0) {
return -1;
}
if (n < 11) {
return PRE_COMPUTED_LEAST_HN[n - 1];
}
size_t sum = n*AVERAGE_VALUE_OF_HEAVY_NUM + 1;
size_t num = 0;
size_t tempDigits = 0;
while (sum) {
if (sum > 9) {
num += 9 * pow(10, tempDigits);
++tempDigits;
sum -= 9;
}
else {
break;
}
}
if ((n - tempDigits) == 1) {
num += sum * pow(10, tempDigits);
}
else {
num += (sum - 1) * pow(10, tempDigits);
num += pow(10, n - 1);
}
return num;
}
// main.cpp
#include "HeavyNumberImpPolynomial.h"
int _tmain(int argc, _TCHAR* argv[])
{
size_t numOfHN;
HeavyNumberImpPolynomial hnp;
numOfHN = hnp.GetNumOfHeavyNumbersAgainstRange(10000, 10000);
numOfHN = hnp.GetNumOfHeavyNumbersAgainstRange(789, 788);
numOfHN = hnp.GetNumOfHeavyNumbersAgainstRange(789, 56788765);
numOfHN = hnp.GetNumOfHeavyNumbersAgainstRange(0, 200000000);
}
//********************************************************************************
Optimization techniques:
- Use pre-calculated values to speed up the process
* The pre-calculated number of heavy number given all n digit numbers
- Narrow the range given all n digit numbers
* The pre-calculated least heavy number given all n digit numbers
- Use hash map to cache the work done so far.
No comments:
Post a Comment