The weekly challenge 352 - Task 2: Binary Prefix

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-352/#TASK2
  3 #
  4 # Task 2: Binary Prefix
  5 # =====================
  6 #
  7 # You are given an array, @nums, where each element is either 0 or 1.
  8 #
  9 # Define x_i as the number formed by taking the first i+1 bits of @nums (from
 10 # $nums[0] to $nums[i]) and interpreting them as a binary number, with $nums[0]
 11 # being the most significant bit.
 12 #
 13 # For example:
 14 #
 15 ## If @nums = (1, 0, 1), then:
 16 ##
 17 ## x0 = 1 (binary 1)
 18 ## x1 = 2 (binary 10)
 19 ## x2 = 5 (binary 101)
 20 ##
 21 ## For each i, check whether x_i is divisible by 5.
 22 #
 23 # Write a script to return an array @answer where $answer[i] is true if
 24 # x_i is divisible by 5, otherwise false.
 25 #
 26 ## Example 1
 27 ##
 28 ## Input: @nums = (0,1,1,0,0,1,0,1,1,1)
 29 ## Output: (true, false, false, false, false, true, true, false, false, false)
 30 ##
 31 ## Binary numbers formed (decimal values):
 32 ##          0: 0
 33 ##         01: 1
 34 ##        011: 3
 35 ##       0110: 6
 36 ##      01100: 12
 37 ##     011001: 25
 38 ##    0110010: 50
 39 ##   01100101: 101
 40 ##  011001011: 203
 41 ## 0110010111: 407
 42 #
 43 #
 44 ## Example 2
 45 ##
 46 ## Input: @num = (1,0,1,0,1,0)
 47 ## Output: (false, false, true, true, false, false)
 48 ##
 49 ##      1: 1
 50 ##     10: 2
 51 ##    101: 5
 52 ##   1010: 10
 53 ##  10101: 21
 54 ## 101010: 42
 55 #
 56 #
 57 ## Example 3
 58 ##
 59 ## Input: @num = (0,0,1,0,1)
 60 ## Output: (true, true, false, false, true)
 61 ##
 62 ##     0: 0
 63 ##    00: 0
 64 ##   001: 1
 65 ##  0010: 2
 66 ## 00101: 5
 67 #
 68 #
 69 ## Example 4
 70 ##
 71 ## Input: @num = (1,1,1,1,1)
 72 ## Output: (false, false, false, true, false)
 73 ##
 74 ##     1: 1
 75 ##    11: 3
 76 ##   111: 7
 77 ##  1111: 15
 78 ## 11111: 31
 79 #
 80 #
 81 ## Example 5
 82 ##
 83 ## Input: @num = (1,0,1,1,0,1,0,0,1,1)
 84 ## Output: (false, false, true, false, false, true, true, true, false, false)
 85 ##
 86 ##          1: 1
 87 ##         10: 2
 88 ##        101: 5
 89 ##       1011: 11
 90 ##      10110: 22
 91 ##     101101: 45
 92 ##    1011010: 90
 93 ##   10110100: 180
 94 ##  101101001: 361
 95 ## 1011010011: 723
 96 #
 97 ############################################################
 98 ##
 99 ## discussion
100 ##
101 ############################################################
102 #
103 # This is a straight forward one: We keep the current prefix number and
104 # calculate the next one as twice the current one plus the added digit.
105 # Then we just need to check whether that number is divisible by 5 and
106 # add either a "true" or a "false" to the result set.
107 
108 use v5.36;
109 
110 binary_prefix(0,1,1,0,0,1,0,1,1,1);
111 binary_prefix(1,0,1,0,1,0);
112 binary_prefix(0,0,1,0,1);
113 binary_prefix(1,1,1,1,1);
114 binary_prefix(1,0,1,1,0,1,0,0,1,1);
115 
116 sub binary_prefix(@nums) {
117     say "Input: (" . join(", ", @nums) . ")";
118     my @output = ();
119     my $current = 0;
120     foreach my $digit (@nums) {
121         $current *= 2;
122         $current += $digit;
123         push @output, $current % 5 ? "false" : "true";
124     }
125     say "Output: (" . join(", ", @output) . ")";
126 }