Well, I've been thinking about it and was determined that there be a faster solution that's more on the bit level, and I think I've found it.
Consider the following table of hexadecimal numbers:
The last row all the numbers are evenly divisible by 3.
In the first row, 0x1 is not divisible by 3, but 0x12, 0x15, 0x18, 0x1b, and 0x1e are divisible by 3. And if we interchange the first digit (0x1) with 0x4, 0x7, 0xa, or 0xd, that is any of the other numbers from row one, the resulting number is still divisible by 3.
In the second row, it's just about the same. 0x21, 0x24, 0x27, 0x2a, 0x2d are all evenly divisible by 3, and the first digit (0x2) can be interchanged with any other number in the second row and still be evenly divisible by 3.
The third row actually doesn't even matter as long as the number of digits from row one equal the number of digits from row two.
Take for instance this large number 0x75F64ED2. Now let's count how many of the digits are from row one, and how many are from row two. All of the digits from row one are one '7', one '4', and one 'D'. From row two we have one '5', one 'E', and one '2'. Now comparing the sum of each together, we'll see that there is an equal number of digits from row one as from row two, which means that the number is evenly divisible by 3.
int row1Count = 0;
int row2Count = 0;
while (input > 0)
{
switch (input & 0xF)
{
case 0x1:
case 0x4:
case 0x7:
case 0xA:
case 0xD:
row1Count++; break;
case 0x2:
case 0x5:
case 0x8:
case 0xB:
case 0xE:
row2Count++; break;
default: break;
}
input >> 4;
}
if (row1Count == row2Count)
std::cout << "The input is divisible by three!";
else
std::cout << "The input is not divisible by three. . .";
Also, if you don't like thinking in hexadecimal, you can also do it in decimal and it's actually easier because the table is smaller:
So take for instance the number 108651. There are two digits from row one and two digits from row two, which means the number is evenly divisible by three. An easy way to remember the table is to visualize a numeric keypad, such as on a telephone, only the rows then become columns.
Now how optimal is this compared to just subtracting 3 and using a list of set endpoints?
Well, you only have to initialize two extra integers instead of a large X amount of integers to mark ranges.
You only have to loop up to a max of 8 times for a 32-bit integer (16 times for a 64-bit integer), but the smaller the number then the smaller the iterations needed, as opposed to subtracting 3 X amount of times, depending on how big your list of numbers-divisible-by-three is and what the numbers in that list are.
I noticed a slight problem with this, but it is fixable. The number 111 is divisible by 3, however the algorithm will return false. So I surmise that if you apply the algorithm to the difference of the two sums continuously until the difference of the two sums is less than 3, then a solution can be met.
germansingergirl
gummygunk
pixelskylines
prguitarman
kianamaiart
2087
yousharknotpass
theartofmadeline