A Rule of Divisibility by 13
When you divide the successive powers of 10 by 13 you get the following remainders of the integer divisions:
1, 10, 9, 12, 3, 4.
Then the whole pattern repeats.
Hence the following method: Multiply the right most digit of the number with the left most number in the sequence shown above, the second right most digit to the second left most digit of the number in the sequence. The cycle goes on and you sum all these products. Repeat this process until the sequence of sums is stationary.
Input Format
An integer greater than or equal to 0 into a function
thirt
contained within a classThirteen
.Output Format
Returns an integer value: the stationary number described above.
To complete the all my test cases one hundred thousand times, it takes 4.7181s
on average of 10 tries. Although this is a decent result for 1.1 million calls of my function, which gives an average of 4.28918μs
per function call, but I'm still a beginner, and I think there is a lot I could do to improve the style, consistency, readability, and efficiency of my code.
I've included many additional comments expressing my main concerns in the code below, though any constructive criticism would be very appreciated.
I wrote this code some time back - uncommented - so there is a section around the middle where I feel things are very dirty, and I don't really understand it, if anyone could shed some light on that it would be great.
Any and all comments would be very appreciated, I want to know exactly what I should do to improve my skills, even if it involves rewriting the entire code.
#include <vector>
#include <cassert>
class Thirteen {
public:
static long long thirt (long long number);
static const std::vector<int> set;
};
// Given set of remainder numbers when powers of 10
// starting from 10^2 are divided by 9, repeating at 10^8.
const std::vector<int> Thirteen::set = {1, 10, 9, 12, 3, 4};
long long Thirteen::thirt (long long number) {
// Set the original for use later, is there a cleaner way of doing this?
long long original = number;
// Organize the numbers into a vector of its digits in reverse order.
std::vector<int> digits = {};
while (number > 0) {
// Get final digit.
int digit = number % 10;
// Insert final digit into the end of the vector.
digits.push_back (digit);
// Remove final digit from the number.
number /= 10;
}
// Create a vector of the products of each digits by their respective multiplier.
std::vector<int> products = {};
int iteration = 0;
// Keep on multiplying until the set runs out.
while (digits.size() > 0) {
// Add the multiplied digit to the products vector:
// - get the digit from the vector set by the iteration number
// - get the multiplier from the iteration modulo the multiplier set size
// - multiply them together and push them to the products vector
products.push_back (digits[iteration] * set[iteration % set.size()]);
// I have no idea how this part works, it just does, and I need help.
// I'm removing the last digit even though I'm iterating from
// the front to the end, and checking the size it is sometimes less
// than the iteration variable, yet the underlying digits vector
// does not throw an out of range exception, it works, but how?
digits.pop_back();
// Iterate to continue to the next digit.
iteration++;
}
// Calculate the total through iterating through the products vector,
// and adding all the products together
int total = 0;
for (int product : products) {
total += product;
}
// Check if the total is equal to the original set before,
// end the function and return the value if it is,
// otherwise, go through another iteration of the function.
// This area seems dirty, I feel like there are much better ways of doing this, any help?
if (total == original) {
return original;
} else {
return Thirteen::thirt (total);
}
}
// TEST CASES BELOW
void Test (int ans, int sol) {
assert(ans == sol);
}
int main () {
for (int i = 0; i < 100000; i++) {
Test(Thirteen::thirt(87), 87);
Test(Thirteen::thirt(0), 0);
Test(Thirteen::thirt(8529), 79);
Test(Thirteen::thirt(85299258), 31);
Test(Thirteen::thirt(5634), 57);
Test(Thirteen::thirt(1111111111), 71);
Test(Thirteen::thirt(987654321), 30);
Test(Thirteen::thirt(1314050335), 39);
Test(Thirteen::thirt(1140681280), 37);
Test(Thirteen::thirt(1449166222), 49);
Test(Thirteen::thirt(1069756634), 11);
}
}