The Sequence Equation Algorithm

Konnichiwa fellow programmers and welcome to another algorithm session!🙂

In this article, I'll be describing how I solved the Sequence Equation Challenge on HackerRank using Python 3.

This challenge is part of the Implementation challenges in the Algorithm section on HackerRank.

If this is your first time reading my data structures and algorithms article, please consider reading more in my Algos in Plain English series.😃

Problem 🎲

Given a sequence of n integers, p(1), p(2),...,p(n) where each element is distinct and satisfies 1 ≤ p(x) ≤ n. For each x where 1 ≤ x ≤ n, that is x increments from 1 to n, find any integer y such that p(p(y)) ≡ x and keep a history of the values of y in a return array.

Example

p = [5, 2, 1, 3, 4]

Each value of x between 1 and 5, the length of the sequence, is analyzed as follows:

The values for y are [4, 2, 5, 1, 3].

Function Description

Complete the permutationEquation function in the editor below.

permutationEquation has the following parameter(s):

• int p[n]: an array of integers

Returns

• int[n]: the values of y for all x in the arithmetic sequence 1 to n

Sample Input:

p = [2, 3, 1]

Sample Output

2
3
1

Explanation

Given the values of p(1) = 2, p(2) = 3, and p(3) = 1, we calculate and print the following values for each x from 1 to n:

Check out the original challenge on HackerRank for more info on input constraints and other sample inputs.

Solution 🔎

In plain English, given an array of distinct numbers, we need to get a number represented by "the index of the index" of the original array of numbers.

This was the best way I thought to solve the problem and I hope this explanation doesn't make you more confused😅. Let's get to it.

Let's write down the steps we'll use to solve this problem.

# Loop through all elements (not the actual numbers) from 1 to [n].
# Get the numbers at [x] indices. call it [p_x].
# Get the second set of numbers at the [p_x] indices.
# Add these numbers to the result array.

Step 1️⃣: Initialising variables 🏁.

1. We'll store the length of the array p in a variable n.
2. We'll store the result array in a variable ppy.

def permutationEquation(p):
    # Write your code here
    n = len(p)
    ppy = []

Step 2️⃣: Getting the first set of numbers 🥇.

We need to loop through the elements 1 ≤ x ≤ n to get the first and second set of values. + 1 is used to offset the start of the increments because python uses zero-based indexing.

def permutationEquation(p):
    # Write your code here
    n = len(p)
    ppy = []

    for x in range(1, (n + 1)):
        p_x = p.index(x) + 1

Step 3️⃣: Getting the second set of numbers 🥈.

Now, we use the values gotten from the first indices as indices to get the second set of values. These are the values to be returned as the solution.

def permutationEquation(p):
    # Write your code here
    n = len(p)
    ppy = []

    for x in range(1, (n + 1)):
        p_x = p.index(x) + 1
        ppy.append(p.index(p_x) + 1)

    return ppy

This challenge made me learn (again) the importance of understanding the requirements of algorithms and making adequate plans before typing away a solution.

That's it! Thanks for reading! 🙂

Hope this article helped with understanding this challenge. Happy Coding!👨🏽‍💻

Nonsocchi🥷🏽