23 August 2024

Challenge 283

Count Unique

• Task 1: Unique Number
• Task 2: Digit Count Value

Task 1: Unique Number

Submitted by: Mohammad Sajid Anwar

---

You are given an array of integers, @ints, where every elements appears more than once except one element.

Write a script to find the one element that appears exactly one time.

Example 1

Input: @ints = (3, 3, 1)
Output: 1

Example 2

Input: @ints = (3, 2, 4, 2, 4)
Output: 3

Example 3

Input: @ints = (1)
Output: 1

Example 4

Input: @ints = (4, 3, 1, 1, 1, 4)
Output: 3

---

Solution

The usual approach to find a unique element in a list would be to count each value and pick those having a count of one. This requires two passes: one over the list and one over the values thereof.

Here we have very special conditions:

• The elements are integers.
• There is only one unique element.

Utilizing these requirement, the task may be solved in a single pass:

• Add the value to a running sum at the first appearance.
• Subtract the value from the running sum at the second appearance.
• Ignore the value at further appearances.

At the end, the running sum will be the sum over all unique numbers. As there shall be only one such number, the sum equals the unique value. Additionally we may count the number of unique numbers and reject lists that do not conform to the requirements.

Using a hash to record each value’s state:

• not seen if there is no corresponding key
• value is 1 after the first appearance
• value is 0 after the second appearance

use strict;
use warnings;

sub unique_number {
    my ($sum, $cnt, %seen) = (0, 0);
    ($seen{$_}, $sum, $cnt) = exists $seen{$_} ?
        (0, $sum - $seen{$_} * $_, $cnt - $seen{$_}) :
        (1, $sum + $_, $cnt + 1) for @_;

    $cnt == 1 ? $sum : undef;
}

See the full solution to task 1.

Task 2: Digit Count Value

Submitted by: Mohammad Sajid Anwar

---

You are given an array of positive integers, @ints.

Write a script to return true if for every index i in the range 0 <= i < size of array, the digit i occurs exactly the $ints[$i] times in the given array otherwise return false.

Example 1

Input: @ints = (1, 2, 1, 0)
Ouput: true

$ints[0] = 1, the digit 0 occurs exactly 1 time.
$ints[1] = 2, the digit 1 occurs exactly 2 times.
$ints[2] = 1, the digit 2 occurs exactly 1 time.
$ints[3] = 0, the digit 3 occurs 0 time.

Example 2

Input: @ints = (0, 3, 0)
Ouput: false

$ints[0] = 0, the digit 0 occurs 2 times rather than 0 time.
$ints[1] = 3, the digit 1 occurs 0 time rather than 3 times.
$ints[2] = 0, the digit 2 occurs exactly 0 time.

---

Solution

In a verbatim interpretation of the task’s description, there is no input that would give true as the result, because

an array of positive integers

cannot conform to the given condition. As the examples contradict the requested positiveness, we should relax the condition to non-negative.

Furthermore, we need to make a decision about the allowed size of the array. The digit i must be in the range 0..9. In a strict view, there cannot be an array having a length larger than 10 as there are no digits beyond 9. On the other hand, we might allow such arrays given that all elements $ints[$k] == 0 for $k > 9. In the following, we’ll consider both views.

Just for checking the condition, either view is simple to implement. However, the far more interesting question is: Which arrays actually fulfill the condition?

Independently of such view, we may come to some insights about valid arrays. The analysis is rather boring and I’ll omit a derivation here.

• $ints[0] must not be 0.
• $ints[-1] must be 0.
• There are at most four non-zero elements in @ints.
• There cannot be any element in @ints be larger than 2 except $ints[0]

Strict

Combining the above insights, there are one a handful of arrays that fulfill the task’s condition under the strict view We may easily check against these:

use strict;
use warnings;

BEGIN {
    @::strict_arr = (
        [1, 2, 1, 0],
        [2, 0, 2, 0],
        [2, 1, 2, 0, 0],
        [3, 2, 1, 1, 0, 0, 0],
        [4, 2, 1, 0, 1, 0, 0, 0],
        [5, 2, 1, 0, 0, 1, 0, 0, 0],
        [6, 2, 1, 0, 0, 0, 1, 0, 0, 0],
    );

    $::strict_re = qr{^(?:@{[join '|', map join(':', @$_), @::strict_arr]})$};
}

sub digit_count_number_strict {
    join(':', @_) =~ $::strict_re;
}

Relaxed

In the relaxed view, we allow arrays having a length larger than 10, but we require $ints[$k] == 0 for $k > 9.

In the strict view we don’t need to care about another aspect of this task: the meaning of Counting digits, as all numbers are below 10 and therefore are identical to digits. Allowing larger lengths, we arrive at numbers of more than one digit, but according to the task we shall count digits. Thus we split each number of @ints into its digits.

Actually there are an infinite number of such arrays as each of the following, for any value of $p >= 0, is valid:

@ints = (10**$p, 2, 1, (0) x (10**$p - $p));

So it looks like we need a true check on the given array in this case.

Solving this special case using ‘PDL’ again.

Creating a ndarray consisting of the digits of the given array, find the number of occurrences of each digit, restrict to values within the length of the array and compare the result to the original array.

use strict;
use warnings;
use PDL;

sub digit_count_number {
    my $l = long @_;
    my $d = long map split(//), @_;
    my ($cnt, $val) = rle $d->qsort;
    ($cnt, $val) = where $cnt, $val, $val < @_;
    my $freq = zeroes $l;
    $freq->index($val) .= $cnt;
    all $l == $freq;
}

See the full solution to task 2.

---

If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.