4 ms·
Since we're over-engineering here, one more optimization is to skip all potential GCDs that are divisible by 2 or 5. Suppose the GCD was divisible by 2, then a
by amyres 2y ago
Since we're over-engineering here, one more optimization is to skip all potential GCDs that are divisible by 2 or 5.
Suppose the GCD was divisible by 2, then all rows would be even. Since the last digit of an even integer is in {0,2,4,6,8} and we need 9 unique numbers in the final column, we know that 4 or 5 of the row numbers must be odd. So the GCD can't be even.
Similarly, the GCD can't be divisible by 5. If it were, all rows numbers would need a 0 or 5 in the final digit.
- lern_too_spel 2y agoWe know that the GCD is divisible by 9 because the sum of the digits for every row is 45.
- Jtsummers 2y agoNot necessarily. The sum of the digits ranges from 36-45, there are 10 possible digits of which 9 will be used. If, say, 5 were the unused number then it would not be divisible by 9.
- amyres 2y agoExactly. The actual solution to the puzzle in question has a GCD not divisible by 9.
- lern_too_spel 2y agoYou're right. I misread the question. It's 9 of the 10 digits 0-9 instead of all 9 digits 1-9 as in sudoku.