The weekly challenge 078: Leader element and Left rotation

This week, The Weekly Challenge offered us a couple of simple tasks, so why not solve it on Monday. Task1: Leader Element. Task 2: Left Rotation.

This week, The Weekly Challenge offered us a couple of simple tasks, so why not solve it on Monday during the breakfast.

Table of Contents

Leader Element

The task reads as:

You are given an array @A containing distinct integers. Write a script to find all leader elements in the array @A. Print (0) if none found. An element is leader if it is greater than all the elements to its right side.

For example:

Input: @A = (9, 10, 7, 5, 6, 1)
Output: (10, 7, 6, 1)

Before solving the task, let me notice that the last element of the input array is considered a leader element too, so there cannot be a case when you can’t find any leaders (well, except when the input data is empty).

My solution is here:

my @a = 9, 10, 7, 5, 6, 1;

for @a.kv -> $i, $v {
    say $v if $v > all(@a[$i^..*]);
}

The most attractive part of it is the use of the so-called all-junctions:

$v > all(@a[$i ^.. *])

No loops, no comparisons with individual elements. Just a single comparison that checks if all of the elements in the range pass the condition.

From the improvements in the syntax, you may want to make the solution a one-liner by using a postfix form of for.

From the efficiency part, you should definitely go from the end of the array so that you do not re-scan the items on each iteration. This idea is illustrated in the next C++ program:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> a = {9, 10, 7, 5, 6, 1};

    auto max = a.back();
    vector<int> leaders = {max};
    for (auto i = a.rbegin(); i != a.rend(); i++) {
        if (*i > max) {
            max = *i;
            leaders.push_back(max);
        }
    }

    for (auto i = leaders.rbegin(); i != leaders.rend(); i++)
        cout << *i << endl;
}

For the sample input array, both programs print the following:

10
7
6
1

Left Rotation

You are given array @A containing positive numbers and @B containing one or more indices from the array @A. Write a script to left rotate @A so that the number at the first index of @B becomes the first element in the array. Similary, left rotate @A again so that the number at the second index of @B becomes the first element in the array.

Example:

Input:
    @A = (10 20 30 40 50)
    @B = (3 4)
Output:
    [40 50 10 20 30]
    [50 10 20 30 40]

Well, let me reveal the solution in Raku 🙂

my @a = 10, 20, 30, 40, 50;
my @b = 3, 4;

say @a.rotate($_) for @b;

Enjoy the language! Start using it today!

* * *

→ GitHub repository
→ Navigation to the Raku challenges post series

4 thoughts on “The weekly challenge 078: Leader element and Left rotation”

  1. Это правда, что Raku медленный? Даже если это так, есть ли надежды на увеличение производительности в будущем? Хочу попробовать, но как-то не хочется писать то, что будет медленно работать не из-за меня 😀

    1. И правда, и неправда одновременно. Относительно медленная — только компиляция. Выполнение вполне себе норм, а в некоторых тестах вполне быстрее перла. Ну и всегда есть возможность прекомпилировать и использовать уже готовый скомпилированный модуль. Ну и не отходя от кассы скажу, что сейчас компилятор очень стабильный, за несколько лет ни разу не падал ни он сам, ни программа.

Leave a Reply to Andrew Shitov Cancel reply

Your email address will not be published. Required fields are marked *