26
1
To find the digital hardness of an integer, take its binary representation, and count the number of times both a leading and trailing
1
can be removed until it either start or ends with a0
. The total number of bits removed is its digital hardness.
That's quite a wordy explanation - so let's break it down with a worked example.
For this example, we'll use the number 3167. In binary, this is:
110001011111
(Note that, during the conversion to binary, you should make sure to strip leading zeroes)
It doesn't start or end with 0
, so we remove 1 pair of bits:
1 1000101111 1
And another:
11 00010111 11
But now there is a 0 at the beginning, so we can't remove anymore 1
pairs. In total, 4 bits we removed, and so 4 is the digital hardness of 3167.
However, for numbers that can be written as 2n-1 for positive n (i.e. contain only 1
in binary representation), 0 will never be reached, and so all the bits can be removed. This means that the hardness is simply the integer's bit length.
The Challenge
You task is to write a program or function which, given a non-negative integer n >= 0
, determines its digital hardness.
You can submit a full program which performs I/O, or a function which returns the result. Your submission should work for values of n
within your language's standard integer range.
Test Cases
Please notify me if any of these are incorrect, or if you'd like to suggest any edge cases to add.
0 -> 0
1 -> 1
8 -> 0
23 -> 2
31 -> 5
103 -> 4
127 -> 7
1877 -> 2
2015 -> 10
Here's the ungolfed Python solution which I used to generate these test cases (not guaranteed to be bug-less):
def hardness(num) -> int:
binary = bin(num)[2:]
if binary.count('0') == 0:
return num.bit_length()
revbin = binary[::-1]
return min(revbin.find('0'), binary.find('0')) * 2
1How does
1
return 1 when there is no0
in it whatsoever? I mean, you can't possibly remove enough 1's from the string to have the it start or end in0
. – busukxuan – 2017-01-06T20:06:08.5672@busukxuan Read the paragraph just before the "The Challenge" heading: for numbers that can be written as 2^n-1 (i.e. contain only 1 in binary representation), 0 will never be reached, and so all the bits can be removed. This means that the hardness is simply the integer's bit length. – FlipTack – 2017-01-06T20:06:58.853
What I mean is that maybe defining the hardness as "until not both sides start with 1" might be more appropriate. – busukxuan – 2017-01-06T20:08:33.617
2@busukxuan you can think of it as the number of ones each side is padded with, before zeroes are reached. – FlipTack – 2017-01-06T20:09:31.423
2To the downvoter who obviously didn't like the edge cases: The hardness is the number of solid (1) bits it is padded with - if the whole thing is solid, then surely it has 100% hardness, its whole bit length? – FlipTack – 2017-01-06T20:18:27.947
1@FlipTack I don't want to influence too much, it's your challenge. I initially understood "hardness" as the maximum number of pairs of outer ones that can be removed, one from each side. But you may be right, if a single one remains at the end, perhaps it should be counted in – Luis Mendo – 2017-01-06T20:24:16.147
Wouldn't the hardness of 103 be 5, as 103 is 1100111 in binary. (theres 5 1's on the end) – Cormac – 2017-01-07T04:55:31.967
@Cormac read the example - you take the
1
s off in pairs, so with 103 you take 4 off before a zero appears at the beginning. – FlipTack – 2017-01-07T08:44:06.820i'm a bit confused - of course the binary representation of "0" is "0", but 0 can also be written as 2^n - 1 for n = 0 ? – peech – 2017-01-09T16:33:37.550
@peech Sorry, I meant to include positive for describing n (0 isn't positive). What I meant is numbers where all the binary digits are
1
. – FlipTack – 2017-01-09T17:05:19.510