| 22 March 2024 | Challenge 261 |
Bits, Digits and Numbers
Task 1: Element Digit Sum
Submitted by: Mohammad Sajid Anwar
You are given an array of integers, @ints.
Write a script to evaluate the absolute difference between element and digit sum of the given array.
Example 1
Input: @ints = (1,2,3,45)
Output: 36
Element Sum: 1 + 2 + 3 + 45 = 51
Digit Sum: 1 + 2 + 3 + 4 + 5 = 15
Absolute Difference: | 51 - 15 | = 36
Example 2
Input: @ints = (1,12,3)
Output: 9
Element Sum: 1 + 12 + 3 = 16
Digit Sum: 1 + 1 + 2 + 3 = 7
Absolute Difference: | 16 - 7 | = 9
Example 3
Input: @ints = (1,2,3,4)
Output: 0
Element Sum: 1 + 2 + 3 + 4 = 10
Digit Sum: 1 + 2 + 3 + 4 = 10
Absolute Difference: | 10 - 10 | = 0
Example 4
Input: @ints = (236, 416, 336, 350)
Output: 1296
Solution
The task will be generalized to an arbitrary base \(b > 1\). For any non-negative integer we have
\[n = \sum_{i=0}^l d_i b^i \ge \sum_{i=0}^l d_i\]and thus there is no need to take the absolute value of the difference between a number and the sum of its digits.
Using some functions from Math::Prime::Util,
the task may be solved in a single statement:
use strict;
use warnings;
use Math::Prime::Util qw(vecreduce vecsum todigits);
sub eds {
my $base = shift;
vecreduce {$a + $b - vecsum todigits $b, $base} 0, @_;
}
See the full solution.
Task 2: Multiply by Two
Submitted by: Mohammad Sajid Anwar
You are given an array of integers, @ints and an integer $start.
Write a script to do the followings:
a) Look for $start in the array @ints, if found multiply the number by 2
b) If not found stop the process otherwise repeat
In the end return the final value.
Example 1
Input: @ints = (5,3,6,1,12) and $start = 3
Output: 24
Step 1: 3 is in the array so 3 x 2 = 6
Step 2: 6 is in the array so 6 x 2 = 12
Step 3: 12 is in the array so 12 x 2 = 24
24 is not found in the array so return 24.
Example 2
Input: @ints = (1,2,4,3) and $start = 1
Output: 8
Step 1: 1 is in the array so 1 x 2 = 2
Step 2: 2 is in the array so 2 x 2 = 4
Step 3: 4 is in the array so 4 x 2 = 8
8 is not found in the array so return 8.
Example 3
Input: @ints = (5,6,7) and $start = 2
Output: 2
2 is not found in the array so return 2.
Solution
The task can be solved in a single pass through the list as we know the target values beforehand: \(\mathit{start}\,\cdot\,2^i\). Actually, we need to know which is the smallest of the target values that is missing from the list. For this end we define a bit vector of target indicators that is all-zero initially. For every target value we encounter, the corresponding indicator bit will be set. Finally, the least significant bit that is not set leads to the requested result.
The core of this implementation is some bit fiddling. In the following “\(\sim\)” is the bitwise NOT and “\(\&\)” the bitwise AND operation.
Determine if an integer is a power of two
\(n\,\&\,(n - 1) = 0 \quad \Leftrightarrow \quad n = 0 \text{ or } n = 2^k\)
Why does this work?
-
Suppose \(n\) is a power of two.
- Its binary representation is a single one-bit followed by zero or more zero-bits.
- Subtracting one turns the one-bit to zero and the following zero-bits (if any) to one.
- There is not a single bit set in both \(n\) and \(n-1\) and thus \(n\,\&\,(n - 1) = 0\).
n: 0 … 0 1 0 … 0 n-1: 0 … 0 0 1 … 1 n&(n-1): 0 … 0 0 0 … 0 -
Suppose \(n\,\&\,(n - 1) = 0\). Let \(n > 0\).
- \(n\) has a least significant one-bit, followed by zero or more zero-bits.
- Subtracting one from \(n\) turns the least significant one-bit to zero and the following (if any) zero-bits to one. None of the bits preceding the least significant one-bit changes.
- As \(n\,\&\,(n - 1) = 0\), all preceding bits must be zero. Therefore the least significant bit in \(n\) is the only one-bit in \(n\) leading to \(n = 2^k\).
n: … x … 1 0 … 0 n-1: … x … 0 1 … 1 n&(n-1): … x … 0 0 … 0 n: … 0 … 1 0 … 0
Determine the value of the least significant bit that is zero:
\(v = (n + 1)\,\&\,\sim n\)
Why does this work?
-
\(n\) is represented as a sequence of arbitrary bits, followed by a zero-bit and zero or more one-bits.
- \(\sim n\) has the arbitrary bits flipped, followed by a one-bit and zero or more zero-bits
-
\(n + 1\) has the zero-bit flipped to one, the following (if any) one-bits flipped to zero and the leading arbitrary bits remain unchanged.
-
Taking into account that \(x \& \neg x = 0\), we find \((n + 1)\,\&\,\sim n = 2^k\)
n: … x … 0 1 … 1 ~n: … ~x … 1 0 … 0 n+1: … x … 1 0 … 0 (n + 1)&~n: … 0 … 1 0 … 0
Implementation
The task can be solved in a single run of some simple steps:
- reject values not divisible by
$start - divide values by
$start - collect the corresponding bit for powers of two
Finally find the value corresponding to the least significant zero-bit in the collected powers.
This gives the required factor for $start.
The false positive power-of-two test for zero does not harm because zero does not account for the collected powers.
use strict;
use warnings;
use experimental 'prototypes';
sub mb2 ($start, @ints) {
my $p = 0;
for my $i (@ints) {
next if $i % $start;
my $c = $i / $start;
$p |= $c unless $c & ($c - 1);
}
$start * (($p + 1) & ~$p);
}
See the full solution.