25
1
To check whether a decimal number is divisible by 7:
Erase the last digit. Multiply it by 2 and subtract from what is left. If the result is divisible by 7, the original number is divisible by 7.
(also described e.g. here)
This rule is good for manual divisibility check. For example:
Is 2016 divisible by 7?
Subtract
6*2
from 201; we get 189. Is this divisible by 7? To check it, let's apply the rule again.Subtract
9*2
from 18; we get 0. Therefore, 2016 is divisible by 7.
In this challenge, you should apply this rule until the divisibility status is obvious, that is, the number is not greater than 70 (however, see below for details). Make a function or a full program.
Input: a positive integer; your code should support inputs up to 32767 (supporting arbitrary-precision integers is a bonus; see below).
Output: an integer (possibly negative), not greater than 70, that is a result of applying the divisibility-by-7 rule zero or more times.
Test cases:
Input Output Alternative output
1 1
10 10 1
100 10 1
13 13 -5
42 42 0
2016 0
9 9
99 -9
9999 -3
12345 3
32767 28 -14
---------- Values below are only relevant for the bonus
700168844221 70 7
36893488147419103232 32 -1
231584178474632390847141970017375815706539969331281128078915168015826259279872 8
Where two possible outputs are specified, either result is correct: the second one corresponds to applying the rule one more time. It's forbidden to apply the rule on a single-digit number: if you erase the digit, nothing (not 0) is left.
Bonus: If your algorithm
- Supports arbitrary-precision integers
- Performs only one pass on the input
- Has space complexity
o(n)
(i.e. less thanO(n)
); and - Has time complexity
O(n)
,
where n
is the number of decimal digits:
Subtract 50% from your code's byte count.
Real bonus:
In addition, if your algorithm reads the input in normal direction, starting from the most significant digit, subtract 50% once again - your score is 25% of your byte count (it seems possible, but I'm not absolutely sure).
Can you please clarify how we have to handle 9 < input < 70? Should we apply the rule at least one time? Or can we just print it out, since its lower than 70 and the divisibility status is obvius? – Denker – 2016-02-14T20:36:38.143
1@DenkerAffe Returning the input as-is is acceptable. I updated the test-case of input=10 to reflect this; that was the idea from the beginning. – anatolyg – 2016-02-14T20:40:04.650
4I wouldn't want to use that rule on
1000000000000000000001
. – Neil – 2016-02-14T20:55:24.2031But what if your language has
long long
s or some equivalent type built in? – SuperJedi224 – 2016-02-14T22:00:16.167@SuperJedi224
long long
in C has fixed width - not enough. Arbirary-width integers are calledbigint
or something like that. Using a built-in bigint type is OK. – anatolyg – 2016-02-14T22:15:58.4031What I was saying was that, in some implementations, it's a 128-bit integer, which is more than big enough for that last test case. – SuperJedi224 – 2016-02-14T22:18:01.487
7-1. Not all languages support arbitrary precision. – March Ho – 2016-02-15T03:54:28.613
1@MarchHo All turing complete languages support arbitrary precision. – Labo – 2016-02-15T09:30:04.333
@MarchHo - most languages support long enough strings to implement the algorithm without needing to convert the input to an integer type. – Toby Speight – 2016-02-15T12:32:09.003
1@Labo pretty sure Turing completeness isn't required for a language to be considered valid here. And in any case, the whole point is that a vast majority of languages do not support arbitrary precision, which the question required. I guess the string implementation kind of alleviates this though. – March Ho – 2016-02-15T13:42:55.317
This would be more interesting if someone found a closed form expression. – rr- – 2016-02-15T13:56:05.147
@rr- It looks funny though. (using alternate output : http://imgur.com/yeNSUhr)
– Paul Picard – 2016-02-15T15:51:15.6631What's the point of the arbitrary precision requirement? It disadvantages languages in which that's difficult to do while providing a boost to most golfing languages which don't need one, and doesn't add anything to the core challenge. – Robert Fraser – 2016-02-15T17:45:52.760
@RobertFraser I need it so I can properly formalize the "bonus" requirement – anatolyg – 2016-02-15T17:49:00.417
1Then why is support for arbitrary precision not a part of the bonus requirement? – Dennis – 2016-02-15T18:05:27.793
@Dennis No reason... I'll move it there! – anatolyg – 2016-02-15T18:07:02.330
I see you've added a bonus. What counts as "reading the input in normal direction", and "Performs only one pass on the input"? Does my dc answer qualify for the bonus? Or does it need to be a digit-by-digit answer?
– Toby Speight – 2016-02-19T09:53:34.423@TobySpeight If it divides a number by 10 repeatedly, it does several passes on the input. – anatolyg – 2016-02-20T19:56:18.697
I think I understand the requirement now - it needs to be digit-at-a-time processing, which won't really work with dc or bc. I've submitted an answer in C that reads input as a string and processes digits in order, which I believe claims the 75% discount.
– Toby Speight – 2016-02-22T09:01:48.837