Peter
Peter Campbell Smith

All about the way
numbers are written

Weekly challenge 258 — 26 February 2024

Week 258: 26 Feb 2024

Task 2

Task — Sum of values

You are given an array of integers, @ints and an integer $k. Write a script to find the sum of values whose index binary representation has exactly $k number of 1-bits set.

Examples


Example 1
Input: @ints = (2, 5, 9, 11, 3), $k = 1
Output: 17

Binary representation of index 0 = 0
Binary representation of index 1 = 1
Binary representation of index 2 = 10
Binary representation of index 3 = 11
Binary representation of index 4 = 100

So the indices 1, 2 and 4 have total one 1-bit sets.
Therefore the sum, $ints[1] + $ints[2] + $ints[3] = 17

Example 2
Input: @ints = (2, 5, 9, 11, 3), $k = 2
Output: 11

Example 3
Input: @ints = (2, 5, 9, 11, 3), $k = 0
Output: 2

Analysis

This seems quite clear: if for example $k is 2 then we need to add together all the members of @int which have an index whose binary representation has exactly 2 bits set. The first of these is 3 == 0b11, then 5 == 0b101, then 6 == 0b110 and so on. So for example 2 above, $ints[3] is the only one of @ints with one of those indices, and the answer is therefore 11, as shown in the example.

It is of course possible for there to be no indices with the required number of bits, and I have assumed that we return 0 in such cases.

My solution loops $j over the members of @ints and for each $j does:

$binary = sprintf('%b', $j);
$bit_count = eval(join('+', split('', $binary)));

The first line uses sprintf to get the binary representation of $j. The second line splits that digit string into an array of 1s and 0s and then joins the array together with '+' signs. For example 10101 would become 1+0+1+0+1. I then eval that to get the required bit count, 3 in this case.

Then if the bit count equals $k I add it into the sum.

Try it 

Try running the script with any input:



example: 3, 1, 4, 1, 5, 9, 2, 6, 5



example: 2

Script


#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-02-26
use utf8;     # Week 258 - task 2 - Sum of values
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

sum_of_values([2, 5, 9, 11, 3], 1);
sum_of_values([2, 5, 9, 11, 3], 2);
sum_of_values([2, 5, 9, 11, 3], 0);
sum_of_values([2, 5, 9, 11, 3], 3);
sum_of_values([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 4);

sub sum_of_values {
    
    my (@ints, $k, $j, $sum, $binary, $bit_count, $explain);
    
    # initialise
    @ints = @{$_[0]};
    $k = $_[1];
    $sum = 0;
    $explain = '';
    
    # loop over @ints
    for $j (0 .. @ints - 1) {
        
        # count bits in index
        $binary = sprintf('%b', $j);
        $bit_count = eval(join('+', split('', $binary)));
        
        # accumulate $sum where $j has $k bits set
        next unless $bit_count == $k;
        $sum += $ints[$j];
        $explain .= qq[$j == 0b$binary, ];
    }
    
    # show results
    say qq[\nInput:  \@ints = (] . join(', ', @ints) . qq[), \$k = $k];
    say qq[Output: $sum] . 
        ($explain ?  ' ∵ ' . substr($explain, 0, -2) : '');
}

Output


Input:  @ints = (2, 5, 9, 11, 3), $k = 1
Output: 17 ∵ 1 == 0b1, 2 == 0b10, 4 == 0b100

Input:  @ints = (2, 5, 9, 11, 3), $k = 2
Output: 11 ∵ 3 == 0b11

Input:  @ints = (2, 5, 9, 11, 3), $k = 0
Output: 2 ∵ 0 == 0b0

Input:  @ints = (2, 5, 9, 11, 3), $k = 3
Output: 0

Input:  @ints = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15), $k = 4
Output: 15 ∵ 15 == 0b1111

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain