DEV Community: Chrysanthus

Explanations for Tasks and Solutions in C++, JavaScript, etc. for the 17 Algorithm Lessons at app-codility-com/programmers

Chrysanthus — Mon, 05 Jan 2026 03:06:49 +0000

Task score : 100% - Correctness : 100% ; Performance : 100%

Detected time complexity : - See particular solution.

Click Links for Explanations of Tasks and Solutions below.

Explanations for Tasks and Solutions in C++ , for the 17 Algorithm Lessons at app-codility-com/programmers

This is part of Complete Data Structures and Algorithms Course.
Do not forget that you should be paid for reading this.
If you have registered at broad-network website, and you have not received any feedback, complain here.
The link is (click):
https://www.broad-network.com/Software/articles/ChrysanthusForcha/dir0/Explanations-in-Cpp-for-17-Algorithm-Lessons-at-app-codility-com-programmers-with-Problems-and-Solutions.htm

Explanations for Tasks and Solutions in JavaScript, for the 17 Algorithm Lessons at app-codility-com/programmers

This is part of Complete Data Structures and Algorithms Course.
Do not forget that you should be paid for reading this.
If you have registered at broad-network website, and you have not received any feedback, complain here.
The link is (click):
https://www.broad-network.com/Software/articles/ChrysanthusForcha/dir0/Explanations-in-JavaScript-for-17-Algorithm-Lessons-at-app-codility-com-programmers-with-Problems-and-Solutions.htm

Explanations for Tasks and Solutions in PHP, for the 17 Algorithm Lessons at app-codility-com/programmers

This is part of Complete Data Structures and Algorithms Course.
Do not forget that you should be paid for reading this.
If you have registered at broad-network website, and you have not received any feedback, complain here.
The link is (click):
https://www.broad-network.com/Software/articles/ChrysanthusForcha/dir0/Explanations-in-PHP-for-17-Algorithm-Lessons-at-app-codility-com-programmers-with-Problems-and-Solutions.htm

Explanations for Tasks and Solutions in C, for the 17 Algorithm Lessons at app-codility-com/programmers

This is part of Complete Data Structures and Algorithms Course.
Do not forget that you should be paid for reading this.
If you have registered at broad-network website, and you have not received any feedback, complain here.
The link is (click):
https://www.broad-network.com/Software/articles/ChrysanthusForcha/dir0/Explanations%20in%20C%20for%2017%20Algorithm%20Lessons%20at%20app-codility-com-programmers%20with%20Problems%20and%20Solutions.htm

Explanations for Tasks and Solutions in Java, for the 17 Algorithm Lessons at app-codility-com/programmers

This is part of Complete Data Structures and Algorithms Course.
Do not forget that you should be paid for reading this.
If you have registered at broad-network website, and you have not received any feedback, complain here.
The link is (click):
https://www.broad-network.com/Software/articles/ChrysanthusForcha/dir0/Explanations-in-Java-for-17-Algorithm-Lessons-at-app-codility-com-programmers-with-Problems-and-Solutions.htm

Explanations for Tasks and Solutions in Go, for the 17 Algorithm Lessons at app-codility-com/programmers

This is part of Complete Data Structures and Algorithms Course.
Do not forget that you should be paid for reading this.
If you have registered at broad-network website, and you have not received any feedback, complain here.
The link is (click):
https://www.broad-network.com/Software/articles/ChrysanthusForcha/dir0/Explanations-in-Go-for-17-Algorithm-Lessons-at-app-codility-com-programmers-with-Problems-and-Solutions.htm

Explanations for Tasks and Solutions in C# (C-Sharp), for the 17 Algorithm Lessons at app-codility-com/programmers

This is part of Complete Data Structures and Algorithms Course.
Do not forget that you should be paid for reading this.
If you have registered at broad-network website, and you have not received any feedback, complain here.
The link is (click):
https://www.broad-network.com/Software/articles/ChrysanthusForcha/dir0/Explanations-in-CS-for-17-Algorithm-Lessons-at-app-codility-com-programmers-with-Problems-and-Solutions.htm

9. Red-Black Trees and B-Trees in C

Chrysanthus — Mon, 10 Nov 2025 15:15:18 +0000

9. At toptal-com : Algorithm : What are Red-Black Trees and B-Trees? What is the best use case for each of them? Use C if necessary. Question, Explanation, Solution.

Both Red-Black Trees and B-Trees are balanced search trees that can be used on items that can have a comparison operator defined on them. They allow operations like minimum, maximum, predecessor, successor, search, insert, and delete, in O(log N) time (with N being the number of elements). Thus, they can be used for implementing a map, priority queue, or index of a database, to name a few examples.

Red-Black Trees are an improvement upon Binary Search Trees. Binary Search Trees use binary trees to perform the named operations, but the depth of the tree is not controlled - so operations can end up taking a lot more time than expected. Red-Black Trees solve this issue by marking all nodes in the tree as red or black, and setting rules of how certain positions between nodes should be processed. This method guarantees that the longest branch isn’t more than twice as long as the shortest branch, so each branch is shorter than 2*log_base2(N).

Read black tree is the ideal structure for implementing ordered maps and priority queues. B-Trees branch into K-2K branches (for a given number K) rather than into 2, as is typical for binary trees. Other than that, they behave pretty similarly to a binary search tree. This has the advantage of reducing access operations, which is particularly useful when data is stored on secondary storage or in a remote location. This way, we can request data in larger chunks, and by the time we finish processing a previous request, our new request is ready to be handled. This structure is often used in implementing databases, since they have a lot of secondary storage access.

8. Design an algorithm that finds the number of ways in which you can traverse N meters

Chrysanthus — Mon, 10 Nov 2025 15:06:49 +0000

8. At toptal.com : Algorithm : Design an algorithm that finds the number of ways in which you can traverse N meters by doing jumps of 1, 2, 3, 4, or 5 meter lengths. Assume that N can be a very large number. What is the resulting complexity? Use C. Question, Explanation, Solution.

Note:
Dynamic Programming will be used.

The sequence of jumps can be of the set m={1} with 1 being maximum.
The sequence of jumps can be of the set m={1, 2} with 2 being maximum.
The sequence of jumps can be of the set m={1, 2, 3} with 3 being maximum.
The sequence of jumps can be of the set m={1, 2, 3, 4} with 4 being maximum.
The sequence of jumps can be of the set m={1, 2, 3, 4, 5} with 5 being maximum.
The sequence of jumps can be of the set m={1, 2, 3, 4, 5, 6} with 6 being maximum.
And so on . . .

The question uses the sequence of jumps, {1, 2, 3, 4, 5} with 5 being maximum. The dynamic programming table (2D array) below, provides sequences from m={} to m={1, 2, 3, 4, 5}. The maximum of each sequence is quoted as m in the table, and even in the code.

A jump means reaching the end of a meter. Traversing a meter also means reaching the end of the meter. For example, given m={1, 2} and N=2 for length of a path (number of meters), there are two ways of traversing the two meters. One way is to jump by 1 step to reach the end of the first meter and then jump another 1 meter to reach the end of the second meter. The other way is just to jump 2 meters at once, in order to reach the end of the second meter.

For all traversing, the end of the last meter is not crossed, except for the case when N=0. When N=0, there is only one way to traverse the 0 meter. Accept that without proof. If m={1}, the number of ways is 1 for N=0. If m={1, 2}, the number of ways is still 1 for N=0. If m={1, 2, 3}, the number of ways is still 1 for N=0; and so on. In this case, the 0 meter is crossed, and that is the only case for crossing the last meter, where in this case, the last meter does not even exist.

"N can be a very large number" means that N is at least 10 times m, where m here, refers to the largest number in the set of m.

Illustration

In this section, it is explained how to produce the 2D dp array using examples of m and N. "dp" means dynamic programming. The main set used is m={1, 2, 3}.

m={1, 2, 3} and different values of N

Let m={1, 2, 3} and N=0
When m={1, 2, 3} and N=0, there is only one way to traverse the N meters (see above).

Let m={1, 2, 3} and N=1
There is only one way which is the jump:
1

Let m={1, 2, 3} and N=2
Two ways:
either
1, 1
or
2

Let m={1, 2, 3} and N=3
Four ways:
either
1, 1, 1
or
2, 1
or
1, 2
or
3

Let m={1, 2, 3} and N=4
Seven ways:
either
1, 1, 1, 1
or
2, 1, 1
or
1, 2, 1
or
1, 1, 2
or
2, 2
or
3, 1
or
1, 3

Note that here, N=4 = 3+1 = m+1, where m in this case is the highest value in the set for m. When m={1, 2, 3} and N=4, the number of ways is the sum of the 3 previous ways, with N=3, N=2 and N=1; which is four + two + one = seven.

With this trend, when m={1, 2, 3} and N=5, the number of ways should be the sum of the 3 previous ways, with N=4, N=3, and N=2; which is seven + four + two = thirteen.

The above illustration has been made with m={1, 2, 3} for different values of N. In the code, these different values of N is actually referred to, with the variable k. The next and last illustration will be done with m={1, 2} for different values of N.

m={1, 2} and different values of N

Let m={1, 2} and N=0

When m={1, 2} and N=0, there is only one way to traverse the N meters (see above).

Let m={1, 2} and N=1
There is only one way which is the jump:
1.
A jump of 2 has excess.

Let m={1, 2} and N=2
Two ways:
either
1, 1
or
2

Let m={1, 2} and N=3
Three ways:
either
1, 1, 1
or
2, 1
or
1, 2

Note that here, N=3 = 2+1 = m+1, where m in this case is the highest value in the set for m. When m={1, 2} and N=3, the number of ways is the sum of the 2 previous ways, with N=2 and N=1; which is two + one = three.

Let m={1, 2} and N=4
Five ways:
either
1, 1, 1, 1
or
2, 1, 1
or
1, 2, 1
or
1, 1, 2
or
2, 2

With this trend, when m={1, 2} and N=4, as can be seen above, the number of ways is the sum of the 2 previous ways, with N=3 and N=2; which is three + two = five.

The above illustration has been made with m={1, 2} for different values of N. In the code, these different values of N is actually referred to, with the variable k.

The strategy for these illustrations can be used to obtain answers for different combinations of the set m and the value N.

The 2D dp Array

The above strategy is used to produce the following two dimensional dp array:

 m/k    0    1    2    3    4    5     6     7     8      9      10     11

 0      ∞    ∞    ∞    ∞    ∞    ∞     ∞     ∞     ∞      ∞      ∞      ∞
 1      1    1    1    1    1    1     1     1     1      1      1      1
 2      1    1    2    3    5    8     13    21    34     55     89     144
 3      1    1    2    4    7    13    24    44    81     149    274    504
 4      1    1    2    4    8    15    29    56    108    208    401    773
 5      1    1    2    4    8    16    31    61    120    236    464    912

Each value for m represents a set for the sequence m, where the variable, m in the table (2D array), represents the highest integer in its set.

The variable, k represents the different values of N in the table (2D array).

The Logical Pattern

Observe from the table that, for a given value of m, the answer for a value of N, is the sum of the previous m answers.

For example, when m={1, 2, 3, 4, 5} and N=7,

answer = 61 = n(7) = 31 + 16 + 8 + 4 + 2 = 61

When m={1, 2, 3, 4} and N=7,

answer = 56 = n(7) = 29 + 15 + 8 + 4 = 56

When m={1, 2, 3} and N=7,

answer = 44 = n(7) = 24 + 13 + 7 = 44

When m={1, 2} and N=7,

answer = 21 = n(7) = 13 + 8 = 21

When m={1} and N=7,

answer = 1 = n(7) = 1 = 1; just count once

When m={} and N=7,

answer = ∞ = n(7) = ∞ = ∞

The first row of the table, with values of infinity, should not be part of the solution (code).

In general,

n[k] = n[k-1] + n[k-2] +  - - - + n[k-m]

This needs a one dimensional array called n, and not a two dimensional array as anticipated above. In the case of m={1, 2, 3, 4, 5} for the question,

n[k] = n[k-1] + n[k-2] + n[k-3] + n[k-4] + n[k-5]

The code solution for the question, should address the last row in the table above (2D dp array), from m=5.

Answer for given m and N
The next question in search of the complete solution, is how to get the next answer (2D array dp cell value) for a particular value of m and N.

The solution for the problem, is to find all the values for a row in the dp table. In the course of doing that, each cell value for a particular m and N is obtained.

*Explanation with Row 3 *
Here, k can take different values up to N (inclusive), but m remains at 3. For quick reference by the reader, row 3 above is retyped here; thus:

1    1    2    4    7    13    24    44    81     149    274    504

where the first number on the left is for k=0. (do not forget that when k=0, the first number in any row is 1.)

k=0
Number of ways of arranging (any sequence) to cross 0, in the set m={1, 2, 3} is given as 1 (see above). Only when N=0, the path can be crossed. Otherwise, the path (traversing) ends at the end of the last meter.

k = 1
Number of ways of arranging (1,) to sum to 1, in the set m={1, 2, 3} is 1. Remember, any of the numbers in the set m={1, 2, 3}, can be used more than once. Also, considering the highest sequence number, 3 as m, then it should be noticed that k is less than m here. This stage has a count of 1, which is equal to k, the lesser of k and m.

k=2
Number of ways of arranging (1, 2) to sum to 2, in the set m={1, 2, 3} is 2. Remember, any of the numbers in the set m={1, 2, 3}, can be used more than once. Also, considering the highest sequence number, 3 as m, then it should be noticed that k is less than m here. This stage has a count of 2, which is equal to k, the lesser of k and m.

The number of ways, 2 can also be obtained by adding the two previous answers of 1 and 1.

k=3
Number of ways of arranging (1, 2, 3) to sum to 3, in the set m={1, 2, 3} is 4. Remember, any of the numbers in the set m={1, 2, 3}, can be used more than once. Also, considering the highest sequence number, 3 as m, then it should be noticed that k is of the same value as m here (so either can be considered the less). This stage has a count of 3, which is equal to k or m (neither of which is the bigger).

The number of ways, 4 can also be obtained by adding the three previous answers of 1, 1 and 2. Henceforth, with increasing value of k, the number of ways (answer), is the sum of the previous three answers, when m={1, 2, 3}.

k=4
Number of ways of arranging (1, 2, 3) to sum to 7, in the set m={1, 2, 3} is 7. Remember, any of the numbers in the set m={1, 2, 3}, can be used more than once. Also, considering the highest sequence number, 3 as m, then it should be noticed that m is less than k here. This stage has a count of 3, which is equal to m, the lesser of k and m.

The number of ways, 7 can also be obtained by adding the three previous answers of 1, 2 and 4.

k=5
Number of ways of arranging (1, 2, 3) to sum to 13, from the set m={1, 2, 3} is 13. Remember, any of the numbers in the set m={1, 2, 3}, can be used more than once. Also, considering the highest sequence number, 3 as m, then it should be noticed that m is less than k here. This stage has a count of 3, which is equal to m, the lesser of k and m.

The number of ways, 13 can also be obtained by adding the three previous answers of 2, 4 and 7.

The answers (number of ways) of the higher values of k are similarly obtained.

The other rows for the 2D dp array are similarly obtained, but with different sets of m (such as m={1,2} and m={1, 2, 3, 4}).

The question for this article, requires that m={1, 2, 3, 4, 5}. The question does not specify any value for N (k), so N=7 is chosen for the code below.

The complete algorithm below, produces the last row of the 2D array above, from k=0 to k=7 and not k=11. The last value (on the right) corresponding to k=7 is returned.

O(N) Code

Remember that N is very large, in order not to result in N^2 number of operations. A summary for the complete algorithm here, is as follows:

Beginning from k=1 with n[k] = 0, add all the previous answers, for the new answers of k, until k=m. After that, add all the previous m answers for the new answer, where k is greater than m, until the variable, i=m (see below). The program is:

    #include <stdio.h>
    #include <math.h>    //for fmin()

    int  ways(int N, int m) {    //m is the maximum sequence number in set, m
        int n[N+1];

        n[0] = 1;    //first value of array n, for N = 0

        for (int k=1; k<=N; k++) {
            n[k] = 0;    //initial sum to obtain cell value
            for (int i=0; i <= fmin(m, k); i++)
                n[k] = n[k] + n[k - i];
        }

        return n[N]; 
    }

    int main(int argc, char **argv) 
    {
        int ret = ways(7, 5);
        printf("%i\n", ret);

        return 0; 
    }

Do not forget to compile the program with a command like:

gcc temp.c -o temp.exe -lm

if linux or its variant (such as Ubuntu) is used, where the switch -lm, ensures that the fmin() function is applicable.

The output is:

This solution has a time complexity of O(N).

Thanks for reading.

7. How would You find the Length of the Longest Common Subsequence of Elements in two Arrays

Chrysanthus — Mon, 10 Nov 2025 14:36:25 +0000

7. At toptal.com : Algorithm : How would you, in general terms, describe dynamic programming? As an example, how would you find the length of the longest common subsequence of elements in two arrays by using this method? Use C. Question, Explanation, Solution.

Description of Dynamic Programming

Dynamic programming is a paradigm for solving optimization problems. It consists of finding solutions for intermediate subproblems, which can be stored and reused for solving the actual problem. Dynamic programming is the best approach for difficult problems that always become trivial once we know the solution for a slightly easier instance of that problem - the intermediate subproblem. Dynamic programming solutions are best represented by a recursive relation, and easily implemented.

If the intermediate subproblems are not overlapping, then we have just a case of Divide and Conquer.

Many dynamic programming problems involves a two dimensional array, also called a matrix or a table. An attempt to deduce a logical pattern in the content of the 2D array is made, before the code of few number of operations, is written from the pattern.

Lesson

The longest common subsequence (LCS) is defined as the longest subsequence that is common to all the given sequences, provided that the elements of the subsequence are not required to occupy consecutive positions within the original sequences. The order of the elements should also be maintained.

Illustration

Subsequences of "abc" are "", "a", "b", "c", "ab", "ac", "bc" and "abc". In general, a string of length n has 2ⁿ subsequences. In this case n is 3. Do not forget that "" of zero length is a subsequence. Note that in a sequence, some characters can be skipped, in the original string.

Longest Common Subsequence Examples
str1 = "abc"; str2 = "acd"
Output: 2
Explanation: The longest subsequence (lcs) which is present in both strings is "ac".

str1 = "aggtab"; str2 = "gxtxayb"
Output: 4
Explanation: The longest common subsequence (lcs) which is present in both strings is "gtab".

str1 = "abc"; str2 = "cba"
Output: 1
Explanation: There are three longest common subsequences of length 1, "a", "b" and "c".

Problem Illustration
Consider the strings: "sandal" with M number of characters, equal to 6, and the string "bananas" with N number of characters equal to 7. Each of these strings is considered an array.

The longest common subsequence of characters is "ana". For "sandal", 'd' is skipped.

The Two Dimensional Dynamic Programming (dp) Array

The dp array is:

                 b    a    n    a    n    a    s
     i/j    0    1    2    3    4    5    6    7

     0      0    0    0    0    0    0    0    0
s    1      0    0    0    0    0    0    0    1
a    2      0    0    1    1    1    1    1    1
n    3      0    0    1    2    2    2    2    2
d    4      0    0    1    2    2    2    2    2
a    5      0    0    1    2    3    3    3    3
l    6      0    0    1    2    3    3    3    3

Explanation of the 2D dp Array
str1, "sandal" has the index , i from 0 to 6 inclusive, for a length of M+1. Index 0 refers to the empty string, "". Index 1 refers to the character, 's' as well as to the backward string "s". Index 2 refers to the character, 'a' as well as to the backward string "sa". Index 3 refers to the character, 'n' as well as to the backward string "san". Index 4 refers to the character, 'd' as well as to the backward string "sand". Index 5 refers to the character, 'a' as well as to the backward string "sanda". Index 6 refers to the character, 'l' as well as to the complete backward string "sandal".

str2, "bananas" has the index , i from 0 to 7 inclusive, for a length of N+1. Index 0 refers to the empty string, "". Index 1 refers to the character, 'b' as well as to the backward string "b". Index 2 refers to the character, 'a' as well as to the backward string "ba". Index 3 refers to the character, 'n' as well as to the backward string "ban". Index 4 refers to the character, 'a' as well as to the backward string "bana". Index 5 refers to the character, 'n' as well as to the backward string "banan". Index 6 refers to the character, 'a' as well as to the backward string "banana". Index 7 refers to the character, 's' as well as to the complete backward string "bananas".

Imagine that there is the string, "b a n a n a s" and the other string "s a n d a l" is sliding under it from left to right. In the following depiction, the common subsequence is the empty string, "":

            "b a n a n a s"
"s a n d a l"

as there is no overlapping between the two strings. At this point, the common subsequence string is "",of zero length. If the lower string is shifted as a whole, one place to the right, the overlapping characters would be 'b' and 'l', and that gives rise to still a zero length common subsequence empty string. If the lower string is then shifted as a whole, one place to the right, the overlapping characters would be "ba" and "al", and that gives rise to a common subsequence string of length 1, with common subsequence character, "a". If the lower string is then shifted as a whole, one place to the right, the overlapping characters would be "ban" and "dal", and that gives rise to still a common subsequence string of length 1, with the common subsequence character, still "a". If the lower string is then shifted as a whole, one place to the right, the overlapping characters would be "bana" and "ndal", and that gives rise to a new common subsequence string of length 2, with the common subsequence "na", and 'd' skipped for the lower string part, "ndal". If the lower string is then shifted as a whole, one place to the right, the overlapping characters would be "banan" and "andal", and that gives rise to a common subsequence string of length 3, with the common subsequence "ana", and 'd' skipped for the lower string part, "andal". From this point, no matter how many steps the lower string is shifted to the right, the length of the common subsequence string will not increase, and their 3 characters will remain the same, in the same order.

And so, the length of the longest common subsequence is 3. The heading for the columns is "'b'a'n'a'n'a's'", with each letter representing a column. Column zero has no header character. All the 7 cells of column zero, each has the value, zero, because there is no overlapping between the two given strings.

In the table, there are 7 rows. The heading for the rows is "'s'a'n'd'a'l'", with each letter representing a row. Row zero has no header character. All the 8 cells of row zero, each has the value, zero, because there is no overlapping between the two given strings.

The variable for the indexes for the rows is i, and the indexes are from 0 to 6. The variable for the indexes for the columns is j, and the indexes are from 0 to 7. Do not confuse between the first useful column of zeros and the row index column with indexes from 0 to 6, in the table. Also, do not confuse between the first useful row of zeros and the column index row with indexes from 0 to 7, in the table.

For the first row of index 1 (i=1), the 's' alone of "sandal" is shifted one horizontal (j) index at a time from the left end of the row to the right end of the row. For each cell, the length of the common subsequence found is noted. This only occurs at the end of the last cell, with length 1. The overlapping same characters here are, the starting 's' in "sandal" and the last 's' of "bananas". At the end of the algorithm, this common 's' is not part of the longest common subsequence. However, the corresponding cell should have the value, 1.

For the second row of index 2 (i=2), "sa" of "sandal" is shifted one horizontal (j) index at a time from the left end of the row to the right end of the row. For each cell, the length of the common subsequence found is noted. This is 1 for dp[2][2], dp[2][3], dp[2][4], dp[2][5], dp[2][6] and dp[2][7]. The preceding cell of dp[2][1] has 0. The 1's are for the letter 'a' in "sa" of "sandal" and "ba" of "bananas".

For the third row (i=3), "san" of "sandal" is moved from the left end to the right end, one horizontal (j) index at a time. The value of 1 in cell dp[3][2] is for the 'a' in "san" of "sandal" and "ba" of "bananas". The rest of the cells in the row have value 2. The 2 is for "an" in "san" of "sandal" and "ban" of "bananas".

The values for the rest of the row cells can be equally determined by inspection.

The Code

It is important to note that the indexes for the words, "sandal" and "bananas", with the indexes for the dp 2D array, have a difference of 1. For example, the i index for 's' in "sandal" is 0, while the dp i index for the same 's' in "sandal" is 1. The j index for 'b' in "bananas" is 0, while the dp j index for the same 'b' in "bananas" is 1. With that scheme, the complete table with the two index scales is:

               b(0) a(1) n(2) a(3) n(4) a(5) s(6)
     i/j    0    1    2    3    4    5    6    7 

     0      0    0    0    0    0    0    0    0
s(0) 1      0    0    0    0    0    0    0    1
a(1) 2      0    0    1    1    1    1    1    1
n(2) 3      0    0    1    2    2    2    2    2
d(3) 4      0    0    1    2    2    2    2    2
a(4) 5      0    0    1    2    3    3    3    3
l(5) 6      0    0    1    2    3    3    3    3

Looking at the columns: Index 3 for example, for second 'a' in "bananas" is dp index 4 - 1. So, to go from a column index to a character index in "bananas", subtract 1, for the same position. j is the variable for dp column indexes.

Looking at the rows: Index 3 for example, for 'd' in "sandal" is dp index 4 - 1. So, to go from a row index to a character index in "sandal", subtract 1, for the same position. i is the variable for dp row indexes.

The Logical Pattern

There are two rules to deduce here, which are alternatives to one another.

Rule 1
Let str1 identify "sandal" and str2 identify "bananas". If for a cell in the 2-dimensional array, the corresponding letters in the rows header ("sandal") and columns header ("bananas") are the same, then in order to obtain the number (answer) for that cell, go to the immediate left-top cell; get the number there and add 1 to it. This is true for the following cells:

For str1[0] = str2[6] = 's' , dp[1][7] = 1 = dp[0][6] + 1 .
For str1[1] = str2[1] = 'a' , dp[2][2] = 1 = dp[1][1] + 1 .
For str1[1] = str2[3] = 'a' , dp[2][4] = 1 = dp[1][3] + 1 .
For str1[1] = str2[5] = 'a' , dp[2][6] = 1 = dp[1][5] + 1 .
For str1[2] = str2[2] = 'n' , dp[3][3] = 2 = dp[2][2] + 1 .
For str1[2] = str2[4] = 'n' , dp[3][5] = 2 = dp[2][4] + 1 .
For str1[4] = str2[1] = 'a' , dp[5][2] = 1 = dp[4][1] + 1 .
For str1[4] = str2[3] = 'a' , dp[5][4] = 3 = dp[4][3] + 1 .
For str1[4] = str2[5] = 'a' , dp[5][6] = 3 = dp[4][5] + 1 .

Rule 2
Rule 2 is the alternative to rule 1. If rule 1 does not hold (the corresponding letters are not the same), then the number (answer) for the cell in question, is the bigger of the two numbers of the immediate left cell and immediate top cell. Note that if the numbers of these two (left and top) cells are the same, the bigger is still that same number.

The ultimate answer for the question, is the number (value) in cell dp[M][N] .

The Program

And so the code is (read the comments as well):

    #include <stdio.h>
    #include <math.h>    //for fmax()

    int  lcs(char * const str1, char * const str2, int M, int N) {    //M for str1 and N for str2
        int dp[M+1][N+1];    //M for rows and N for columns

for (int i=0; i<(M+1); i++)    //initialize first column
    dp[i][0] = 0;
for (int j=0; j<(N+1); j++)    //initialize first row
    dp[0][j] = 0;

        for (int i=1; i<(M+1); i++) {
            for (int j=1; j<(N+1); j++) {
                if (str1[i-1] == str2[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = fmax(dp[i-1][j], dp[i][j-1]);
            }
        }

        return dp[M][N]; 
    }

    int main() 
    {
        char * const str1 = "sandal";
        char * const str2 = "bananas";

        int ret = lcs(str1, str2, 6, 7);
        printf("%i\n", ret);

        return 0; 
    }

The output is:
3
Do not forget to compile the program with a command like:

gcc temp.c -o temp.exe -lm

if Linux or its variant (such as Ubuntu) is used, where the switch -lm, ensures that the fmax() function is applicable.

The time complexity for the solution is O(MxN). The space complexity is also given as O(MxN).

Thanks for reading.

6. Find all positive numbers in the array that have their opposites in it as well

Chrysanthus — Mon, 10 Nov 2025 11:18:28 +0000

6. At toptal.com : Algorithm : A numeric array of length N is given. We need to design a function that finds all positive numbers in the array that have their opposites in it as well. Describe approaches for solving optimal worst case and optimal average case performance, respectively. Use C. Question, Explanation, Solution.

Solution:

Note:

Three approaches will be addressed in this article: approach for O(N²) time, approach for O(N log2 N) time, and approach for O(N) time. Only the approach for O(N.log2N) time will be described in detail.

Also not that absolute value means the value without sign, which is just the positive value.

O(N²) Solution

With this solution, for each positive number, it is verified (compared) if any other number in the array is the opposite. The number of opposite pairs gives the answer. This solution has O(N²) time complexity. Any good computer programmer can code this solution, so it will not be addressed any further, in this article.

O(N.log2N) Solution

Consider the example list:

-7, 4, -3, 2, 2, -8, -2, 3, 3, 7, -2, 3, -2

By inspection, though inspecting is rather time consuming, the answer is [2, 2, 3, 7]. The subset (-2, -2, 2, 2) produces 2 pairs; the subset (-3 3) produces 1 pair; and the subset (-7 7) produces the last pair, making 4 pairs altogether. The set (-2, -2, 2, 2) has the pairs (-2, 2) and (-2, 2) which is same pair occurring twice.

Need for Special Custom Sorting
The special custom sorting is as follows:

If the numbers are not equal or opposite, they are sorted by their absolute value; but if they are (else), they are sorted by their sign. This leads to the following special custom sort (arrangement):

-2, -2, -2, 2, 2, -3, 3, 3, 4, -7, 7, -8

The 4 pairs required can be seen or inferred.

This is not ordinary sort ascending or ordinary sort descending. A compare function is needed for this special custom sorting. The sort function will use the compare function. The code for this compare function is given along with the principal code below.

Principal Code
There is an issue with this problem and its solution at toptal.com/algorithms/interview-questions. At toptal.com/algorithms/interview-questions, the answer is [2 3 7 ] instead of [2, 2, 3, 7] . This means that the problem actually requires unique positive numbers and not just positive numbers with opposites. The principal code below produces unique positive numbers.

Complete Program

The complete program is (read the comments as well):

    #include <stdio.h>
    #include <stdlib.h>     //for abs() and qsort() functions

    //compare function
    int compareFn(const void *a, const void *b) {
        int int_a = *((int *)a);
        int int_b = *((int *)b);
        if (int_a != int_b && int_a != -int_b)
        return abs(int_a) > abs(int_b);    //from stdlib.h library
    else
            return int_a > int_b;
    }

    //principal code
    void find_numbers_with_opposites(int A[], int N) {
        qsort(A, N, sizeof(int), compareFn);    //from stdlib.h library
        for (int i=1; i<N; i++) {
        if (A[i] > 0 && A[i - 1] == -A[i])
                printf("%i ", A[i]);
        }
    }

    int main(int argc, char **argv)
    {
        int A[] = {-7, 4, -3, 2, 2, -8, -2, 3, 3, 7, -2, 3, -2};
        int N = sizeof(A) / sizeof(A[0]);    //no. of elements in A
        find_numbers_with_opposites(A, N);
        printf("\n");

        return 0;
    }

This implementation has an optimal average case runtime complexity of O(N.log2N), with the sorting algorithm being the bottleneck.

O(N) Solution

This solution needs a hash function. The C language does not have a hash function. The C++ language has a hash function. So only the pseudo code using a hash function is provided below, so that anyone who has studied C++ can implement it. The pseudo code is:

FUNCTION find_numbers_with_opposites(numbers)
    table = HashTable<number, number>
    answer = List
    FOR number IN numbers
        IF number == 0
            CONTINUE
        END IF
        key = abs(number)
        IF key not in table
            table[key] = number
        ELSE IF table[key] = -number
            answer.push(key)
            table[key] = 0
        END IF
    END FOR

Thanks for reading.

4. Advantages, Best, Average, and Worst Case Solutions of Some Sort Algorithms-at-toptal-com-algorithms

Chrysanthus — Mon, 10 Nov 2025 10:42:19 +0000

4. At toptal-com : Algorithm : What are the key advantages of Insertion Sort, Quicksort, Heapsort and Mergesort? Discuss best, average, and worst case time and memory complexity. Question, Explanation, Solution.

Solution:

Note:

Memory complexity means space complexity.

n^2 means n² .

Insertion Sort
Insertion Sort has an average and worst runtime of O(n^2), and a best runtime of O(n). It doesn’t need any extra buffer, so space complexity is O(n). It is efficient at sorting extremely short arrays due to a very low constant factor in its complexity. It is also extremely good at sorting arrays that are already “almost” sorted. A common use is for re-sorting arrays that have had some small updates to their elements.

The other three algorithms have a best and average runtime complexity of O(n log n). Heapsort and Mergesort maintain that complexity even in worst case scenarios, while Quicksort has worst case performance of O(n^2).

Quicksort
Quicksort is sensitive to the data provided. Without usage of random pivots, it uses O(n^2) time for sorting a full sorted array. But by swapping random unsorted elements with the first element, and sorting afterwards, the algorithm becomes less sensitive to data that would otherwise cause worst-case behavior. Though it doesn’t have lower complexity than Heapsort or Merge sort, it has a very low constant factor to its execution speed, which generally gives it a speed advantage when working with lots of random data.

Heapsort
Heapsort has reliable time complexity and doesn’t require any extra buffer space. As a result, it is useful in software that requires reliable speed over optimal average runtime, and/or has limited memory to operate with the data. Thus, systems with real time requirements and memory constraints benefit the most from this algorithm.

Merge Sort
Merge sort has a much smaller constant factor than Heapsort, but requires O(n) buffer space to store intermediate data, which is very expensive. Its main selling point is that it is stable, as compared to Heapsort which isn’t. In addition, its implementation is very parallelizable.

Equivalent Articles

Click: 4. Advantages, Best, Average, and Worst Case Solutions of Some Sort Algorithms-at-toptal-com-algorithms. Algorithm, Question, Explanation, Solution, at toptal.com . Use C# (C-Sharp) if necessary (equivalent article)

Next Article in C: 6. Find all positive numbers in the array that have their opposites in it as well

3. How do Insertion sort, Heapsort, Quicksort, and Merge sort work?

Chrysanthus — Mon, 10 Nov 2025 10:28:14 +0000

At toptal.com, Algorithm, Use C if necessary. Question, Explanation, Solution.

Solution

Insertion Sort
Insertion sort takes elements of the array sequentially, and maintains a sorted subarray to the left of the current point. It does this by taking an element, finding its correct position in the sorted array, and shifting all following elements by 1, leaving a space for the element to be inserted.

Heapsort
Heapsort builds a binary heap. A binary max heap is a nearly complete binary tree in which each parent node is larger or equal to its children. The heap is formed by sifting elements up in the given binary tree (given array). The heap is stored in the same memory in which the original array elements were. Once the heap is formed, that is binary max heap. The opposite is binary min heap.

Quicksort
The Quick Sort algorithm is notable for its approach to sorting an array. Quick Sort begins by selecting a pivot from the provided list, then separates the remaining elements into two groups - those less than the pivot and those greater than it, keeping their order in the initial array. This process is replicated recursively until the entire list is sorted.

Merge Sort
Merge Sort recursively halves the given array. Once the subarrays reach trivial length, merging begins. Merging takes the smallest element between two adjacent subarrays and repeats that step until all elements are taken, resulting in a sorted subarray. The process is repeated on pairs of adjacent subarrays until we arrive at the starting array, but sorted.

Click: 3. How do Insertion sort, Heapsort, Quicksort, and Merge sort work? Algorithm, Question, Explanation, Solution, at toptal.com . Use C# (C-Sharp) if necessary (equivalent article)

Click: 3. How do Insertion sort, Heapsort, Quicksort, and Merge sort work? Algorithm, Question, Explanation, Solution, at toptal.com . Use Java if necessary (equivalent article)

Click: 3. How do Insertion sort, Heapsort, Quicksort, and Merge sort work? Algorithm, Question, Explanation, Solution, at toptal.com . Use C++ if necessary (equivalent article)

Click: 3. How do Insertion sort, Heapsort, Quicksort, and Merge sort work? Algorithm, Question, Explanation, Solution, at toptal.com . Use Python if necessary (equivalent article)

Click: 3. How do Insertion sort, Heapsort, Quicksort, and Merge sort work? Algorithm, Question, Explanation, Solution, at toptal.com . Use JavaScript if necessary (equivalent article)

Click: 3. How do Insertion sort, Heapsort, Quicksort, and Merge sort work? Algorithm, Question, Explanation, Solution, at toptal.com . Use Go if necessary (equivalent article)

Click: 3. How do Insertion sort, Heapsort, Quicksort, and Merge sort work? Algorithm, Question, Explanation, Solution, at toptal.com . Use PHP if necessary (equivalent article)

Next Article in C: 4. Advantages, Best, Average, and Worst Case Solutions of Some Sort Algorithms-at-toptal-com-algorithms

2. Optimal Calculation for pk, where k is a Non Negative Integer, at toptal-com algorithms-interview in C

Chrysanthus — Mon, 10 Nov 2025 08:32:17 +0000

2. At toptal.com : Algorithm : How would you optimally calculate p^k, where k is a non-negative integer? What is the complexity of the solution? Use C. Question, Explanation, Solution.

Solution:
Note:

p^k means p^k .

(p^a)^b = p^(a*b) = p^k , where k = a*b and * means, times.

P^x x p^y = p^(x+y) = p^k , where here, k = x+y.

Lesson

Even Number of the Same Base

3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 3⁸ = 6561

The index, 8 is an even number. There are 7 operations (7 steps) in this mathematical statement (extreme left expression).

Now,

3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 3⁸ = 6561

=> (3 x 3) x (3 x 3) x (3 x 3) x (3 x 3) = 3² x 3² x 3² x 3² = A x A x A x A = A⁴ = (3²)⁴ = 3⁸ = 6561, where A = 3 x 3 = 3² .

But 4 = 2 x 2

∴ 3⁸ = (3²)⁴ = ((3²)²)² = 3⁸ = 6561

i.e. 3⁸ = ((3²)²)² = (3²)⁴ = 3^2x4 with a = 2 and b = 4. Should be programmed recursively, in

((3²)²)² = ((9)²)² = (81)² = 6561 .

There are three operations here, which are the powers: x2x2x2 . So, 7 operations (approximately 8 operations) have been reduced to 3 operations.

So, by dividing 8 (k) by 2 to give 4 and then by 2 to give 2, all the power indexes are obtained, which are the prime number, 2, and for 3 operations.

Here, k = 8.

It is done recursively as follows:

3 x 3 = 9

9 x 9 = 81

81 x 81 = 6561 (three operations, i.e. three steps)

This is because,

3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 3⁸ = 6561

=> (3 x 3) x (3 x 3) x (3 x 3) x (3 x 3) = 3⁸ = 6561

=> 9 x 9 x 9 x 9 = 3⁸ = 6561

=> (9 x 9) x (9 x 9) = 3⁸ = 6561

=> 81 x 81 = 3⁸ = 6561

Odd Number of the Same Base

3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 3⁹ = 19683

The index, 9 is an odd number. There are 8 operations (8 steps) in this mathematical statement (extreme left expression).

Now,

3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 3⁹ = 19683

=> 3 x (3 x 3) x (3 x 3) x (3 x 3) x (3 x 3) = 3 x 3² x 3² x 3² x 3² = 3 x A x A x A x A = 3 x A⁴ = 3A⁴ = 3(3²)⁴ = 3 x 3⁸ = 19683, where A = 3 x 3 = 3² .

But 4 = 2 x 2

∴ 3⁹ = 3(3²)⁴ = 3((3²)²)² = 3 x ((3²)²)² = 3 x 3⁸ = 3¹ x 3⁸ = 3¹ x 3^9-1 = 19683

i.e. 3⁹ = 3 x ((3²)²)² = 3¹ x 3⁸ = 3¹ x 3^9-1 with x = 1 and y = 9-1. Should be programmed recursively, in

3 x ((3²)²)² = 3 x ((9)²)² = 3 x (81)² = 19683 .

There are three main operations here, which are 3x and the powers: 2x2x2 . So, 8 operations have been reduced to 3 operations.

Do not forget that, here, k = 9 here.

Remarks

For an even value of k, choosing a = 2 and b = k/2, thus having p^k = (p^2)^(k/2), will reduce the number of required multiplications considerably. For an odd value of k, choosing x = 1 and y=k-1 will result in y being even, and the same process as for the even case, can then simply be repeated. This allows the definition of a recursive function.

Time complexity

The time complexity for this scheme is O(log2k), as opposed to the brute-force scheme of O(k).

Code in C

The program in C uses a recursive function. The program is:

   #include <stdio.h>

    int powe(int base, unsigned int exponent) {
        if (exponent == 0)
            return 1;
        else if (exponent % 2 == 0)    //exponent is even
            return powe(base * base, exponent / 2);
        else    //exponent is odd
            return base * powe(base * base, (exponent - 1) / 2);
    }

    int main(int argc, char **argv)
    {
        int k = 8;
        int ret1 = powe(3, k);
        printf("%i\n", ret1);

        int k2 = 9;
        int ret2 = powe(3, k2);
        printf("%i\n", ret2);

        return 0; 
    }

The output is:

6561

19683

and correct. For the first function call, the base is 3 and k is 8. For the second function call, the base is still 3 and k is 9.

Note that the C predefined function, pow() has not been used. The core of the code is (base * base, exponent / 2) for even k and (base * base, (exponent - 1) / 2) for odd k, either of which has just one multiplication.

This one multiplication is done three times as follows: 3 x 3 = 9; 9 x 9 = 81; 81 x 81 = 6561.

For the first multiplication, the exponent, 8 is divided by 2 to give an integer division quotient of 4. For the second multiplication, the new exponent, 4 is divided by 2 to give an integer division quotient of 2. For the third multiplication, the new exponent, 2 is divided by 2 to give an integer division quotient of 1. A fourth division attempted would result in the new exponent, 1 being divided by 2 to give an integer division quotient (whole number) of 0; ending the recursion at the first function body statement. Remember that p⁰ is 1.

So, the dividing of the exponent is checking the number of times the division has to be done.

Thanks for reading.

Click: 2. Optimal Calculation for pk, where k is a Non Negative Integer, at toptal-com algorithms-interview in C# (equivalent article)

Click: 2. Optimal Calculation for pk, where k is a Non Negative Integer, at toptal-com algorithms-interview in Java (equivalent article)

Click: 2. Optimal Calculation for pk, where k is a Non Negative Integer, at toptal-com algorithms-interview in C++ (equivalent article)

Click: 2. Optimal Calculation for pk, where k is a Non Negative Integer, at toptal-com algorithms-interview in Python (equivalent article)

Click: 2. Optimal Calculation for pk, where k is a Non Negative Integer, at toptal-com algorithms-interview in JavaScript (equivalent article)

Click: 2. Optimal Calculation for pk, where k is a Non Negative Integer, at toptal-com algorithms-interview in Go (equivalent article)

Click: 2. Optimal Calculation for pk, where k is a Non Negative Integer, at toptal-com algorithms-interview in PHP (equivalent article)

Next Article in C: 3. How do Insertion sort, Heapsort, Quicksort, and Merge sort work?

1.What are Divide and Conquer algorithms?

Chrysanthus — Mon, 10 Nov 2025 02:49:56 +0000

1. At toptal.com : Algorithm : What are Divide and Conquer algorithms? Describe how they work. Can you give any common examples of the types of problems where this approach might be used? Use C if necessary. Question, Explanation, Solution.

Solution:
Divide and Conquer algorithms are a paradigm for solving problems that involve several basic steps. First, we divide the problem into smaller pieces and work to solve each of them independently. That is, divide given list into smaller parts, and work to solve each of them independently. Once we’ve solved all of the pieces, we take all of the resulting smaller solutions and combine them into a single integrated comprehensive solution. This second stage is the conquering stage.

This process can be performed recursively; that is, each "sub problem" can itself be subdivided into even smaller parts if necessary. This recursive division of the problem is performed until each individual problem is small enough to become relatively trivial to solve.

Some common examples of problems that lend themselves well to this approach are binary search, sorting algorithms (e.g., Merge Sort, Quicksort), optimization of computationally complex mathematical operations (Exponentiation, FFT, Strassen’s algorithm), and others.

Click: 1. What are Divide and Conquer Algorithms? – in C# (equivalent article)

Click: 1. What are Divide and Conquer Algorithms? – in Java (equivalent article)

Click: 1. What are Divide and Conquer Algorithms? – in C++ (equivalent article)

Click: 1. What are Divide and Conquer Algorithms? – in Python (equivalent article)

Click: 1. What are Divide and Conquer Algorithms? – in JavaScript (equivalent article)

Click: 1. What are Divide and Conquer Algorithms? – in Go (equivalent article)

Click: 1. What are Divide and Conquer Algorithms? – in PHP (equivalent article)

Next Article in C: 2. Optimal Calculation for pk, where k is a Non Negative Integer, at toptal-com algorithms-interview in C

OddOccurrencesInArray at app.codility.com/programmers in C Explained: Find value that occurs in odd number of elements.

Chrysanthus — Mon, 22 Sep 2025 00:29:50 +0000

Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N) or O(N*log(N))
Lesson 2 at app.codility.com/programmers
Task, solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm

Task

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9

    the elements at indexes 0 and 2 have value 9,
    the elements at indexes 1 and 3 have value 3,
    the elements at indexes 4 and 6 have value 9,
    the element at index 5 has value 7 and is unpaired.

Write a function:

int solution(int A[], int N);

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9

the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

    N is an odd integer within the range [1..1,000,000];
    each element of array A is an integer within the range [1..1,000,000,000];
    all but one of the values in A occur an even number of times.

Note
The above list has been arranged as follows:

Element:    9   3   9   3   9   7   9
Index :     0   1   2   3   4   5   6

The paired elements are 9 and 3. This can be deceiving. An algorithm code written, based on this setup, would not work for other setups, for the same criteria and conditions of the task (problem). The paired elements could have been 9, 3, and 8; as in the following arrangement:

Element:    9   3   9   3   8   7   8
Index :     0   1   2   3   4   5   6

This can still be deceiving because, for each pair, the second element occurs after one element. That is: for the pair of 9, the second 9 occurs after 3; for the pair of 3, the second 3 occurs after 9; for the pair of 8, the second pair occurs after 7. An algorithm code written, based on this arrangement, would not work for other arrangements, for the same criteria and conditions, of the task (problem). The arrangement could otherwise have been in still a slightly more deceiving form as follows:

Element:    9   9   3   3   8   8   7
Index :     0   1   2   3   4   5   6

There are still other deceiving arrangements.

Efficient Algorithm

The last three line conditions in the given problem above, are not really to be verified, by the code of the student (candidate). It should be assumed that they are implied in the given data.

It can be unnecessarily difficult to write the function in a brute force way. A fast (efficient) algorithm is to sort the vector (array), and then find the element that does not have a pair (adjacent); in a final one scan of the vector. That element would be in an odd number position. The program is (read the code and comments):

#include <stdio.h>
#include <stdlib.h>

int compFn(const void *a, const void *b) {
    int int_a = *((int *)a);
    int int_b = *((int *)b);
    return int_a - int_b;
}

int solution(int A[], int N) {
    if (N == 1)
        return A[0];
    else { 
        qsort(A, N, sizeof(int), compFn);
        for (int i=0; i<N-2; i+=2) {
            if (A[i] != A[i+1])
                return A[i];  //0 is odd for zero based indexing
        }
    }
    return A[N-1];  
}

int main() 
{ 
    int B[] = {9, 3, 9, 3, 9, 7, 9};
    int N = sizeof(B) / sizeof(B[0]);    //divide size of array by size of one (first) element

    int odd = solution(B, N);

    printf("%i\n", odd);

    return 0; 
}

Note: the qsort() function is from the stdlib (sub) library.

Note: with zero based indexing, index 0 is odd, index 2 is odd, index 4 is odd, etc.

The qsort function is a predefined function in the C standard library (actually the stdlib sub library). It needs a compare function (compFn() in this case) that compares two numbers. The compare function, receives as arguments, two memory addresses, 'a' and b. In the compare function, (int *)a for example, means, put the address as value into a pointer object (variable). *((int *)a) means, return the value pointed to, by the pointer object (int *)a.

What matters with the compare function is, that a positive value is returned, or zero is returned or a negative value is returned.

It is the predefined qsort() function that calls the user defined compFn() function, by sending it two references (addresses); and the programmer (developer) should not border about the definition of the references. The last argument of the qsort function call, is the user defined compare function, compFn without the parentheses.

The output is 7, as expected. Read through the code if that is not already done.

Remember, at codility.com/programmers, the C main function is not typed (sent). The solution code begins with the determination of the number of elements in the vector. There after, if the array contains only one element, then the one element is not paired, and it is returned.

Otherwise, the list is sorted, and scanned from the beginning. After sorting, as the list is scanned, paired elements occur next to one another. And so there has to be a for-loop that increments by 2 (i+=2) and not 1. The unpaired element will be found in an odd position. If the last element is the unpaired element, it will be returned by the second return-statement.

For the given array

    int B[] = {9, 3, 9, 3, 9, 7, 9};

after sorting, the array is:

    int B[] = {3, 3, 7, 9, 9, 9, 9};

The element that is not paired is 7, and it is in the third position, which is zero-based index 2 (ordinal position - 1 = zero based index). With zero-based indexing, 0 is in an odd position, which is the first ordinal position; and one is in an even position. The reader should not confuse between zero-based index positioning and normal cardinal positioning of: 1, 2, 3, 4, 5. etc. With normal cardinal positioning, 2 is in an even position, while with zero-based index positioning, 2 is in an odd position (actually third ordinal position).

Note that the while-condition in the for-loop is (i<N-2).

If the unpaired value is at the end of the list, it is still returned, because in the body of the for-loop, A[i] is compared with A[i+1] , and zero-based indexing ends at N-1.

The reader should register at app.codility.com/programmers to be testing his/her own code.

That is it, for the explanation of the task.

For C++ click: OddOccurrencesInArray at app.codility.com/programmers in C++ Explained: Find value that occurs in odd number of elements.

For JavaScript click: OddOccurrencesInArray at app.codility.com/programmers in JavaScript Explained: Find value that occurs in odd number of elements.

Next article in the series: Coming Soon !

CyclicRotation at app.codility.com/programmers in C Explained: Rotate an array to the right by a given number of steps.

Chrysanthus — Mon, 22 Sep 2025 00:10:16 +0000

Task score : 100% - Correctness : 100% ; Performance : not assessed
Lesson 2 at app.codility.com/programmers
Task, solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm

Task

An array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7] - elements are shifted right by one index and 6 is moved to the first place .

The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.

Assume that the following declarations are given:

struct Results {
  int * A;
  int N; // Length of the array
};

Write a function:

struct Results solution(int A[], int N, int K);  //prototype

that, given an array A consisting of N integers and an integer K, returns the array A rotated K times.

For example, given

A = [3, 8, 9, 7, 6]
K = 3

the function should return [9, 7, 6, 3, 8]. Three rotations were made:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

For another example, given

A = [0, 0, 0]
K = 1

the function should return [0, 0, 0]

Given

A = [1, 2, 3, 4]
K = 4

the function should return [1, 2, 3, 4]

Assume that:

    N and K are integers within the range [0..100];
    each element of array A is an integer within the range [−1,000..1,000].

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

Brute Force Approach

The brute force approach is to shift each element in the array one place to the right, and the last element to the first place, for each pass, through the array. The brute force approach is accepted for this particular test, CyclicRotation; and it is used below. A struct with an integer sequence called, A is returned instead of an array, in the following program. The code, which the reader should read through, is:

#include <stdio.h> 

struct Results {
    int * A;
    int N; // Length of the array
} stroct;

struct Results solution(int A[], int N, int K) {
    stroct.A = &A[0];    //stroct.A and A[] now point to the same address;
    stroct.N = N;

    for(int i=0; i<K; i++) {
        if (N > 0) {
            int temp = A[N-1];
            //shift right by 1 index
            for (int j=N-1; j>0; j--) {    //end at j == 1
                A[j] = A[j-1];
            }
            A[0] = temp;  //put last value in 1st place
        }
    }

    return stroct;
}

int main() 
{ 
    int N = 5;
    int B[] = {3, 8, 9, 7, 6};
    int K=3;
    struct Results str = solution(B, N, K);
    for (int i=0; i < str.N; ++i)
        printf("%i ", str.A[i]);

    return 0; 
}

Note: Since the C function cannot return an array, a struct (Results str) with an integer sequence called A, is retuned instead.

The output is: 9 7 6 3 8, as expected. Read through the code, if that is not already done.

At app.codility.com/programmers, the score for correctness is 100%, for this function. Note that at app.codility.com, the main() C function is not typed (not sent to the server). At app.codility.com/programmers there is a score out of 100% for correctness, and also a score out of 100% for performance (reduced time complexity). Some middle value is taken as the total task score, still out of 100%. For this particular task, no mark is given for performance.

The reader should register at app.codility.com/programmers to be testing his/her own code.

That is it, for the explanation of this task.

For C++ click: CyclicRotation at app.codility.com/programmers in C++ Explained: Rotate an array to the right by a given number of steps.

For JavaScript click: CyclicRotation at app.codility.com/programmers in JavaScript Explained: Rotate an array to the right by a given number of steps.

Next article in the series: OddOccurrencesInArray at app.codility.com/programmers in C Explained: Find value that occurs in odd number of elements.

Arrays Explanation for app.codility.com/programmers in C

Chrysanthus — Sun, 21 Sep 2025 23:58:35 +0000

Category of Article : Technology | Computers and Software | Algorithm

An array is a list structure that can be used to store many items in one place. In C, the items have to be of the same type. Imagine that there is a list of items; for example, a shopping list. The items are listed in one column or in one row on a paper. Such a column or row is conceptually similar to an array. Similarly, if air temperatures for each day in a locality, are planned to be recorded over the next 365 days, then all the temperatures would be recorded in one array. The array will have 365 data entries.

Creating an Array

One way to create an array is as shown in the following program:

#include <stdio.h>

char *arr[] = {"bread", "butter", "cheese"};

int main(int argc, char** argv)
{

    return 0;
}

The first and last code segments must be there. The single middle code segment of one statement is what creates the array. It begins with the data type of the elements for the array. In this case, the data type is a string, which should have been included among the pre-processing directives. arr is the name of the array and should be followed by the square brackets, to indicate that the variable is an array. Each shopping item is in a pair of double quotes. These quotes are not the word processor quotes; they are quotes of the text editor. The items are separated by commas. There is no comma after the last item. The array literal or initializer_list is delimited by braces (curly brackets). This is separated from the left hand side of the statement, by the assignment operator (=).

The first three lines of the program, have to be there. These are pre-processing directives. The first line include the stdio.h library for input and output (keyboard/terminal). The next line includes the string library, for the string class (data type). The third line used, insists that any namespace used, is of the standard namespace. The fourth line, creates the array, with the array literal on the right of the assignment (=) operator. This has the shopping items as strings. The last code segment is the C main function, which has to be there. This function in its current form, has the minimum of its coding. Note the function parameters and the return statement, that have to be there.

The statement (fourth) above that creates the array, is both a declaration and a definition. It is a definition because of the initializer_list (array literal). A declaration is a definition, but a definition is not necessarily a declaration. A definition is an optional sub-part of a declaration, that puts items in memory.

A array can be declared as a simple declaration, without the array literal. In this case it is not really a definition. Also, the number of array items must be included in the square brackets, when it is not a definition. If 3 items are to be in the array, then the simple creation statement would be:

    char *arr[3];

In theory, this created array is empty.

Giving an Array, Elements

When an array is created with the initializer_list, the elements (values) are already given. If the array is created with just a simple declaration and not effectively defined, then the array values have to be given, for the different elements as follows:

#include <stdio.h>

char *arr[3];

int main(int argc, char **argv)
{
    arr[0] = "bread";
    arr[1] = "butter";
    arr[2] = "cheese"; 

    return 0;
}

An array can be seen as different variables next to one another, but with the same name. The actual different variables are differentiated by indexes. Index counting begins from 0, and not 1. The index for a particular value is in square brackets, just after the array name.

Note that though the simple declaration has been made outside of the C main() function, the assignment of the values have been made inside the C main() function. Assignment of any value is not allowed outside any function, in C .

Accessing Array Values

Array values in C can only be read one-by-one. This is done using the subscript notation (index in square brackets). The syntax is:

type variable = arrayName[index];

The following code segment will output "butter" after the array has been created:

    char *var = arr[1];
    printf("%s\n", var);

This code segment should be in the C main() function or in any other function, below the creation of the array (with values given). The printf statement sends the value of var to the terminal (screen) and then sends the cursor (I-bar, flashing) to the next line below, at the output.

It has been explained above, how to set (give) value to an array element.

Modifying an Array

The elements of a C array can only be modified, one-by-one. The subscript notation is still used. The syntax is:

arrayName[index] = value;

The value has to be of the same type as all the array elements. The following code segment will output "chocolate paste" instead of "cheese", after the above array has been created:

    arr[2] = "chocolate paste";
    printf("%s\n", arr[2]);

The output is "chocolate paste". This code segment has to be in the C main() function or in any other function, below the creation of the array (with values given).

The index corresponding to the array value "cheese" is 2. "cheese" was replaced.

In C, once an array has been created, its length cannot be changed. This means that a new item cannot be added after the last item of the array.

The length of an array can also not be reduced, once created.

Iterating over an Array

The do-while-loop
The following program, shows a do-while-loop in C :

#include <stdio.h>

char *arr[] = {"bread", "butter", "cheese"};

int main(int argc, char **argv)
{
    int i = 0;
    do 
        {
            printf("%s\n", arr[i]);
            i = i + 1;  //increment: add 1
        } while (i<3);

    return 0;
}

Note that the do-while-loop is in the C main() function and not outside of any function. The array is not declared (and defined) inside any function. It could still have been defined inside the C main() function or any other function.

The output consists of each of the array elements, beginning from the first, then second and then third.

The do-while-loop has a block, delimited by curly brackets (braces). The "do" reserved word is in front of this block. The loop uses a variable, i that is incremented for each pass, through the block.

The statements in the block are executed over and over, in the order typed. The while-condition is that, the block should stop executing, when the value of i is just below 3, that is 2. The first statement in the block prints out an array value. The second statement increments i (adds 1). The block is executed 3 times; when i is 0; i is 1; and i is 2. i was initialized to 1, in front of the do-while-loop.

With the do-while-loop, the block is executed before the while-condition is checked. Note that the do-while-loop construct ends with a semicolon, just after the while-condition "(i<3)".

The While-Loop
The while-loop is similar to the do-while-loop. With the while-loop, the while-condition is checked before the loop body (block) is executed, for each iteration. With the do-while-loop above, the body is executed first, before the while-condition is checked, for each iteration. The following while-loop code segment would replace the above do-while-loop code segment (would do the same thing):

    int i = 0;
    while (i<3)
        {
            printf("%s\n", arr[i]);
            i += 1;  //increment: add 1
        }

Note that the while-loop construct does not end with a semicolon after, '}'. Also note the alternative increment statement, "i += 1;", which is the same as "i = i + 1;"

The for-Loop
The while-loop has a difference with the do-while-loop. The for-loop is another way of coding the while-loop. The above while-loop code segment would be coded with the for-loop as follows:

#include <stdio.h>

char *arr[] = {"bread", "butter", "cheese"};

int main(int argc, char **argv)
{
    for (int i = 0; i<3; i += 1)
        {
            printf("%s\n", arr[i]);
        }

    return 0;
}

The for-loop begins with the reserved word, "for" with all letters in lowercase. Then there is the parentheses. In the parentheses, there are three statements, with the last one not ending with a semicolon. The last statement is the increment statement, which has been transferred from the body of the while-loop, to this position. The middle statement is the while-condition. The first statement is the initialization of i to 0; it is no longer outside the construct. There is now only one statement in the body of this loop (for-loop). The output here, is the same as in the previous cases.

Conclusion
An array can be created as the following two code segments show:

string arr[] = {"bread", "butter", "cheese"};

string arr[3];
arr[0] = "bread";
arr[1] = "butter";
arr[2] = "cheese";

The array can be handled with subscripts (index in square brackets).

For C++ click: Arrays and Vectors Explanation for app.codility.com/programmers in C++

For JavaScript click: Array Explanation for app.codility.com/programmers in JavaScript

Next article in the series: CyclicRotation at app.codility.com/programmers in C Explained: Rotate an array to the right by a given number of steps.

DEV Community: Chrysanthus

Explanations for Tasks and Solutions in C++, JavaScript, etc. for the 17 Algorithm Lessons at app-codility-com/programmers

Task score : 100% - Correctness : 100% ; Performance : 100%

Detected time complexity : - See particular solution.

Click Links for Explanations of Tasks and Solutions below.

9. Red-Black Trees and B-Trees in C

9. At toptal-com : Algorithm : What are Red-Black Trees and B-Trees? What is the best use case for each of them? Use C if necessary. Question, Explanation, Solution.

8. Design an algorithm that finds the number of ways in which you can traverse N meters

8. At toptal.com : Algorithm : Design an algorithm that finds the number of ways in which you can traverse N meters by doing jumps of 1, 2, 3, 4, or 5 meter lengths. Assume that N can be a very large number. What is the resulting complexity? Use C. Question, Explanation, Solution.

Illustration

The 2D dp Array

The Logical Pattern

O(N) Code

7. How would You find the Length of the Longest Common Subsequence of Elements in two Arrays

7. At toptal.com : Algorithm : How would you, in general terms, describe dynamic programming? As an example, how would you find the length of the longest common subsequence of elements in two arrays by using this method? Use C. Question, Explanation, Solution.

Description of Dynamic Programming

Lesson

Illustration

The Two Dimensional Dynamic Programming (dp) Array

The Code

The Logical Pattern

The Program

6. Find all positive numbers in the array that have their opposites in it as well

Solution:

O(N2) Solution

O(N.log2N) Solution

Complete Program

O(N) Solution

4. Advantages, Best, Average, and Worst Case Solutions of Some Sort Algorithms-at-toptal-com-algorithms

4. At toptal-com : Algorithm : What are the key advantages of Insertion Sort, Quicksort, Heapsort and Mergesort? Discuss best, average, and worst case time and memory complexity. Question, Explanation, Solution.

Solution:

3. How do Insertion sort, Heapsort, Quicksort, and Merge sort work?

At toptal.com, Algorithm, Use C if necessary. Question, Explanation, Solution.

Solution

2. Optimal Calculation for pk, where k is a Non Negative Integer, at toptal-com algorithms-interview in C

2. At toptal.com : Algorithm : How would you optimally calculate p^k, where k is a non-negative integer? What is the complexity of the solution? Use C. Question, Explanation, Solution.

Lesson

Remarks

Time complexity

Code in C

1.What are Divide and Conquer algorithms?

1. At toptal.com : Algorithm : What are Divide and Conquer algorithms? Describe how they work. Can you give any common examples of the types of problems where this approach might be used? Use C if necessary. Question, Explanation, Solution.

OddOccurrencesInArray at app.codility.com/programmers in C Explained: Find value that occurs in odd number of elements.

Task

Efficient Algorithm

CyclicRotation at app.codility.com/programmers in C Explained: Rotate an array to the right by a given number of steps.

Task

Brute Force Approach

Arrays Explanation for app.codility.com/programmers in C

Creating an Array

Giving an Array, Elements

Accessing Array Values

Modifying an Array

Iterating over an Array

O(N²) Solution