DEV Community: Chrysanthus

1.2 Time Complexity Explained in C

Chrysanthus — Sun, 21 Jun 2026 04:28:48 +0000

1. Time and Space Complexity in C

Full Course on Data Structures and Algorithms in C

The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Time Complexity refers to how fast a piece of code (a function for example, and not the whole program) runs from beginning to completion. Since different computers have different microprocessor clock frequencies and different sizes of memory, the same code will take different durations to run in different computers. Because of this issue and others, time complexity is given as relative speed.

Time complexity is the maximum number of main operations the piece of code needs, to solve a type of problem, in the worst case situation. There is Constant Time Complexity, Linear Time Complexity, Logarithmic Time Complexity, Quadratic Time Complexity, Exponential Time Complexity and Factorial Time Complexity.

A typical way to express time complexity, is with the Big-O notation, of which examples are given below.

Constant Time - O(1)

Consider the following function:

    void solution() {
        int result = 5 + 5;
        printf("%i\n", result);
    }

There are two statements in the body of the function, solution(). After compilation, these statements are in binary code, of more than two lines, but still not of many lines. These two statements are executed in a short time. This is known as constant time, written in Big-O notation as O(1), where the 1 in parentheses means, short duration or constant time. The exact time in milliseconds (seconds), is not emphasized upon, in the topic, time complexity. Constant time operation is best considered as one main operation.

Linear Time - O(n)

The above two statements can be considered as the main operation for the above function code. Consider the following function:

    void solution() {
        int N = 8;
        for (int i=0; i<N; i++) {
            printf("%i ", i);
        }
        printf("\n");
    }

The for-loop displays 8 numbers, which are:

0 1 2 3 4 5 6 7

Though the statement, "printf("%i ", i);" takes slightly longer to execute than a previous statement, "int N = 8;" or the last statement, "printf("\n");" , it is the statement of interest, and it is executed (N = 8) times. The statement of interest, "printf("%i ", i);" is the main operation, in this function.

Time complexity is the number of main operations in some piece of code. It is actually the maximum possible number of main operations in the code. In this situation, the first and last statements, "int N = 8;" and "printf("\n");" respectively, are ignored, when quoting the time complexity. They are also ignored, because they do not repeat. The repeating main operation, is called the dominant operation. Using the Big-O notation, the time complexity for this function is given as,

O(n)

where n in this case is 8. This is linear time, which can be appreciated as one complete scan of a list (consecutive counting).

Logarithmic Time – O(log n)

The mathematical symbol, =>, means “this implies that”.

Now,
8 = 2 x 2 x 2
=> 8 = 2³

In this second math statement, 2 is called the base, 3 is called the index and 8 is just called the number (number of interest). So 8 equals 2 raised to the power (index) 3, because 2 is multiplied by itself 3 times to give 8.

The second mathematical statement above, can be rewritten as:

        log₂ 8 = 3

read as, log to the base 2 of 8 equals 3. The word, log, is of the math topic, logarithm. There are three mathematical statements above (in this section). The second and third are two different ways of writing the same thing. The two different ways, each has its pros and cons.

From out of 8 possible repetitions of the main operation in a function, if the main operation repeats 3 times, then the time complexity is written as:

O(log₂ n)

using the Big-O notation, where n in this case is 8. The subscript 2 is optional to write. The logarithmic time, O(log n) is usually less than half the linear time, O(n), e.g 3 is less than half of 8, which is 4.

For code example of logarithmic time, with the number 8, consider the following function:

    void solution() {
        int N = 8;
        while (N > 1) {
            N = N / 2;  //integer division
            printf("%i, ", N);
        }
        printf("\n");
    }

The main operation consists of the two statements:

            N = N / 2;  //integer division
            printf("%i, ", N);

With integer division (N / 2), the remainder is abandon after each division. The output is:

4, 2, 1,

That is, out of 8 possible operations, there are 3 operations, corresponding to the 3 numbers at the output. With time complexity, what matters is the number of main operations, and not necessarily, the number of numbers at the output. In this situation, the number of numbers at the output happens to be the same as the number of main operations (number of round loopings (iterations)). For each loop repeat, the main operation executes in constant time, O(1). For the 3 repeats, the function takes logarithmic time, O(3) as opposed to linear time O(8), out of 8 operations.

Quadratic Time - O(n²)

In the alphabet, A, B, C, D, E, F, G, H are characters, and each is less than (comes before) 'I'. Consider the following function:

    void solution() {
        for (char i='A'; i<'I'; i++) {
            for (char j='A'; j<'I'; j++) {
                printf("%c ", j);
            }
            printf("\n");
        }
    }

There are two for-loops, with one nested in the other. The inner-loop prints a row of 8 characters. The outer-loop enables the printing of 8 of these rows. The output is:

    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H

This is an 8-by-8 table. The number of characters are 64 = 8 x 8. The main operation is 'printf("%c ", j);', which executes 8 x 8 times = 64 = 8²; that is 8 square. Squaring means quadratic. So the time complexity for this function is written as:

O(n²)

where n is 8 in this case. 8² = 8 x 8. This is quadratic time complexity.

n.log₂n Time

n.log₂n means, n x log₂n . The mathematical symbol, ∴ means, therefore.

From above,

      8 = 2 x 2 x 2
=>    8 = 2³
=>   log₂ 8 = 3

Now,

    if n = 8, then O(n²) = 64 operations = O(8²).

    if n = 8, it means log2 8 = 3;
    ∴ n x log2n = 8 x 3 = 24

64 = 8²

There are 24 main operations for (8xlog₂ 8) time. 24 is less than half of 64, which is 32. 24 is greater than 3, which equals log₂8

So, O(n.log₂n) time complexity lies between O(log₂n) and half of O(n²) , generally.

For code example of O(n.log₂n) time, with the number 8, consider the following function:

    void solution() {
        int N = 8, Q = 8;
        for (int i=0; i<Q; i++) {
            while (N > 1) {
                N = N / 2;  //integer division
                printf("%i, ", N);
            }
            printf("\n");
            N = 8;
        }
    }

The main operation consists of the two statements:

                N = N / 2;  //integer division
                printf("%i, ", N);

With integer division, the remainder is abandon after each division. The while-loop does the main operation, 3 times. The for-loop does what is in the while-loop 8 times. This makes 8 x 3 = 24. The exact time complexity from O(n.log₂n) here, is O(8.log₂ 3) . The output is:

    4, 2, 1, 
    4, 2, 1, 
    4, 2, 1, 
    4, 2, 1, 
    4, 2, 1, 
    4, 2, 1, 
    4, 2, 1, 
    4, 2, 1,

There are 8 rows and 3 columns, giving 24 output entries; in this case, corresponding to 24 main operations.

n + m Linear Time : O(n + m)

For code example of n + m linear time, with the number n = 8, consider the following function:

    void solution() {
        int start = 1;
        for (int i=start; i<8; i++) { 
            printf("%i ", i);
        }

        printf("\n");

        for (char i='A'; i<'J'; i++) {  //'I' is 9th letter in alphabet
            printf("%c ", i);
        }
        printf("\n");
    }

The main operation is "printf("%i ", i);" or "printf("%c ", i);" for either non-nested for-loops. The output is:

    1 2 3 4 5 6 7
    A B C D E F G H I

The first for-loop in the code, produces 7 out of 8=n main operations. The second for-loop in the code, produces 9 out of 8=n main operations. The first set of main operations is referred to as, n operations; and the second set of main operations is referred to as, m operations. Here, n + m = 7 + 9 = 16 (or about 16).

Here, n + m = 16 operations lies between the particular time complexity O(log₂ 8) = 3 operations, and the particular time complexity O(8.log₂ 8) = 24 operations. n + m time generally lies between O(log₂ n) time and O(n.log₂ n) time.

Even if there were three non nested for-loops, as in the following code, the time complexity would still be given as O(n + m) :

    void solution() {
        int start = 1;
        for (int i=start; i<8; i++) { 
            printf("%i ", i);
        }
        printf("\n");
        char ch = 'A';
        for (char i='A'; i<'I'; i++) {  //'I' is 9th capital letter in alphabet
            printf("%c ", i);
        }
        printf("\n");
        char c = 'a';
        for (char i='a'; i<'j'; i++) {  //'j' is 10th small letter in alphabet
            printf("%c ", i);
        }
        printf("\n");
    }

The output is:

    1 2 3 4 5 6 7
    A B C D E F G H 
    a b c d e f g h i

Nuance to do with ½n, 2n, etc.

In an algorithm where the upper limit is 8 = n (linear time), 4 main operations = ½n or 16 main operations = 2n, is given simply as O(n). In other-words, fractions and multiples (coefficients) in front of time complexity expressions are avoided.

Exponential Time Complexity : O(2ⁿ)

21 = 2
22 = 2 x 2
23 = 2 x 2 x 2
24 = 2 x 2 x 2 x 2
25 = 2 x 2 x 2 x 2 x 2

This is generally written as:

2ⁿ = 2 x 2 x 2 - - - x nᵗʰ2

2ⁿ is called the nᵗʰ power of 2. Time complexity of O(2⁵) means, there are 2⁵ = 2 x 2 x 2 x 2 x 2 = 32 main operations. In general, O(2ⁿ) means, there are 2ⁿ operations (maximum).

Multiplication is continuous addition; so 2⁵ = 2 x 2 x 2 x 2 x 2 = 32, is the same as:

    1 + 1 +
    1 + 1 + 
    1 + 1 + 1 + 1 + 
    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 
    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

The main operation is just addition. There are 31 addition operations here. However, as concerns time complexity, the number of additions are assumed to be 32 (upper limit).

The following function is supposed to be for 2⁵ main operations, of time complexity, O(2⁵), and generalized as O(2ⁿ) . The first two main operations are outside the nesting loop.

    void solution() {
        int n = 5;

        int number = 1 + 1;
        int sum = 1 + 1;
        for (int i=2; i <= n; i++) {
            for (int j=1; j <= sum; j++) {    //last 3 rows above, approached in halves
                number = number + 1;
            }
            sum = number;
        }
        printf("%i\n", number);
    }

The output is 32. The statements, "int number = 1 + 1;" and "int sum = 1 + 1;" form the first two main operations in the code of interest. There are twenty eight more coded additions, each of which is just the addition of 1. The statements in the parentheses of the nesting for-loops are ignored, in determining the time complexity. The statements, "sum = number;" and 'printf("%i\n", number);' are also ignored. The reader should read through the function again, to really understand what is going on.

The code does 30 coded additions in the nested for-loop, and two additions outside the nesting for-loop; but the 5 rows of manual additions of 1’s, has 31 addition operations. That is how time complexity is, sometimes. The time complexity for this situation, is given as O(2⁵), and generalized as O(2ⁿ).

Factorial Time Complexity : O(n!)

Now,

      5! = 5 x 4 x 3 x 2 x 1 = 120
=>    5! = 120

Notice that x1 (times 1) does not change the previous product of x2.

Multiplication is continuous addition; so the above is the same as:

    (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) = 20 +

    (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) = 40 +

    (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) = 60 +

    (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) = 80 +
    (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) = 100 +
    (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) + (1 + 1 + 1 + 1 +1) = 120

All the 1’s counted in this series gives 120. However, there are 119 addition operations in the series. Accept that.

The 1’s are in two groups for x2 (times 2). The first group has 1’s in three rows for x3. Each row is five 1’s times four. The second group also has 1’s in three rows . Each row is five 1’s times four.

The following function is for 5! = 120 main operations, of time complexity, O(5!), and generalized as O(n!) . The first main operation is outside the nesting for-loop.

    void solution() {
        int n = 5;
        int newAddition = 5;
        int oldAddition = 5;

        int factorial = 0;
        for (int i = n; i>1; i--) {
            for (int j=1; j <= newAddition; j++) {
                factorial = factorial + 1;
            }
            newAddition = factorial * (i - 1) - oldAddition;
            oldAddition = factorial * (i - 1);  //5 x 4 = 20, then 20 x 3 = 60. then 20 x 2 = 120. x1 (times 1) does not change the previous product of x2
        }
        printf("%i\n", factorial);
    }

The output is 120. There are 119 addition operations in the code. The time complexity is given as O(120), and not O(119), and generalized as O(n!). Accept that. The main operation is "factorial = factorial + 1;", where factorial is just a variable; and the rest of the operation statements in the code, are ignored, in the quotation of time complexity – accept that. If n = 4, then all the values of 5 in the code, have to be changed to 4. The reader should read through the function to really understand what is going on.

Time limit

Nowadays, an average computer can perform 10⁸ operations in less than a second. Sometimes the programmer has the information he needs about the expected time complexity, but at other times the programmer does not.

During contests, the candidate is often given a limit on the size of data; and therefore he can estimate the time complexity within which the task should be solved. This is usually a great convenience because he can look for a solution that works in a specific time complexity, instead of worrying about a faster solution. For example, at codility.com, if the size of the data:

    -  n <= 1 000 000, the expected time complexity is O(n) or O(n log n),
    -  n <= 10 000, the expected time complexity is O(n² ),
    -  n <= 500, the expected time complexity is O(n³ ).

Of course, these limits are not precise. They are just approximations, and will vary depending on the specific task.

Approximation of Time Complexity

Time complexity, of O(10) may actually have 8 or 9 operations, or even 11 or 12 operations, or the 10 itself, though the maximum limit of 8 is aimed at. In many cases it would have 8 operations or less.

Exercise

Problem 1: You are given an integer n. Count the total of 1 + 2 + . . . + n, in O(n²) time.
Solution
The following program has one test case in the main() function (read the code and comments in the whole program). In the function, 1 is 1; 2 is 1 + 1; 3 is 1 + 1 + 1; 4 is 1+1+1+1; etc.

    #include <stdio.h>

    int slow_solution (int N) {  //using zero based indexing 
        int result = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j < i+1; j++) {  //i=0 or j=0 refers to the first element, 1
                result += 1;               //i=1 or j=1 refers to the second element, 2, etc.
            }
        }

        return result;
    }

    int main(int argc, char **argv)
    {
        int n = 4;
        int res = slow_solution(n);
        printf("%i\n",res);

        return 0;
    }

The output is 10, for input of N = 4.

Problem 2: Repeat the above problem for the time complexity of O(n).
Solution
The following program has one test case in the main() function (read the comments in the whole program). The function does 1 + 2 + 3 + 4 = 10.

    #include <stdio.h>

    int fast_solution (int N) {  //using zero based indexing 
        int result = 0;
        for (int i=0; i<N; i++) {
            result = result + (i + 1);  //1=0+1; 2=1+1; 3=2+1; etc.
        }

        return result;
    }

    int main(int argc, char **argv)
    {
        int n = 4;    //1 + 2 + 3 + 4 = 10
        int res = fast_solution(n);
        printf("%i\n",res);

        return 0;
    }

The output is 10; same as above, for input of N = 4.

Problem 3: Repeat the above problem for the constant time complexity, O(1).
Solution
This is a mathematical Arithmetic Progression, with the first term, a = 1, and common difference, d = 1. The sum, Sₙ of the first n terms, of an arithmetic progression, is given by,

    Sₙ = n/2[2a + (n-1)d]

This formula is one main operation and should be coded as such. The following program has one test case in the main() function (read the comments for the whole program):

    #include <stdio.h>

    int model_solution (int n) {  //formula: sum of arithmetic progression, with first element, 1 and difference, 1

        int result = n/2*(2*1 + (n-1)*1);  //one operation, without repetition in any loop

        return result;
    }

    int main(int argc, char **argv)
    {
        int n = 4;  //sum = n/2*(2*1 + (n-1)*1)
        int res = model_solution(n);
        printf("%i\n",res);

        return 0;
    }

The output is 10; same as above, for input of N = 4. There is only one main operation here.

Space Complexity

Memory limits provide information about the expected space complexity. The programmer can estimate the number of variables that he can declare in his programs. In short, if he has constant numbers of variables, he also has constant space complexity: in Big-O notation this is O(1). If he needs to declare an array with n elements, he has linear space complexity - O(n).

More specifically, space complexity is the amount of memory needed to perform the computation. It includes all the variables, both global and local, dynamic pointer data-structures, and in the case of recursion, the contents (space) of the stack. Depending on the convention, input data may also be included. Space complexity is more tricky to calculate than time complexity, because not all of these variables and data-structures may be needed at the same time. Global variables exist and occupy memory all the time; local variables (and additional information kept on the stack) will exist only during invocation of the function. There are also temporary variables needed by the algorithm.

In many problems, it is the time complexity that is expected to be met, and the space complexity limit is not indicated.

Whatever is the case, space complexity is explained in the next part of the series.

Conclusion

The time complexity of a piece of code, is the number of main operations in the code. This is a good indication of how fast the code will run on a particular system (computer). The main operation may consist of one, or two or three simple statements.

If the main operation consists of many statements, then single statements sprinkled here and there in the code, will be ignored in the quotation of the time complexity.

1.1 Looping in C

Chrysanthus — Fri, 19 Jun 2026 04:22:02 +0000

1. Time and Space Complexity in C

Full Course on Data Structures and Algorithms in C

The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

In programming, iterating means repeating some part of the code to obtain different results. This involves looping.

A loop is a compound statement whose body can be executed again and again. The body of the loop has a number of statements. A loop needs an initial state or initial statement, from which the loop will execute the first time, before repeating. Repeating, means all the statements in the body of the loop are re-executed, in order, again and again. In order for the loop to repeat after the first pass or any pass of the body, there has to be a statement that will cause it to repeat. In order for a loop to stop repeating, there has to be a condition that will cause the loop not to repeat./p>

This tutorial presents basic programming constructs that allow iterations to be performed in C (in a loop). The names of the different loops are: the do-while loop, the while-loop and the for-loop.

Do-while Loop Syntax

The syntax for the do-while loop construct is:

//initial statement here (initialization)
do {
    //statements
    //cause for next iteration (continue Statement)
} while (condition);

This construct should be read as follows: Considering the initial statement, do all the statements in the loop, while the condition allows it. The initial statement ends with a semicolon. The do-compound statement itself, also ends with a semicolon. Note that “while” here, is a reserved word.

There are three main loops in C: the do-while loop, the while-loop and the for-loop. This tutorial (lesson ) explains the do-while loop, the while-loop and the for-loop.

do-while Loop Example

Using the above syntax, an example of a do-while loop coding, is in the following program:

#include <stdio.h>

int main(int argc, char **argv) {
    int myInt = 0;
    do {
        printf("%d ", myInt);
        myInt++;
    } while (myInt < 5);

    printf("\n");
    return 0;
}

The output is:

0 1 2 3 4

The complete construct begins with “int myInt = 0;” and ends at “while (myInt < 5);”. There are two simple statements in the braces. The first statement in the braces, prints out the value of the integer, myInt. The second statement increments myInt, by adding 1 to it. The condition is “while (myInt < 5)”. So, while myInt is less than 5, the compound statement is re-executed.

This loop has just one main simple statement, which is to print the value of myInt. The second simple statement is to cause the next iteration. The curly brackets can have more than one main simple statement. The following do-while loop has two main simple statements. The first one adds 2 to myInt, and the second one prints the result of the addition:

#include <stdio.h>

int main(int argc, char **argv) {
    int myInt = 0;
    do {
        myInt = myInt + 2;
        printf("%d ", myInt);
        myInt++;
    } while (myInt < 13);
    printf("\n");
    return 0;
}

The output is:

2 5 8 11 14

This output needs explanation. First of all, note that the while condition has been changed to "while (myInt < 13)".

When myInt is 0, 2 is added to it, and myInt becomes 2. Two is printed. The increment adds 1 to myInt and it becomes 3, at the beginning of the next pass. In the next iteration (pass) myInt is 3. Two is added to it again and it becomes 5. The increment adds 1 to myInt and it becomes 6. In the next iteration myInt is 6. Two is added to it again and it becomes 8. The increment adds 1 to myInt and it becomes 9. In the next iteration myInt is 9. 2 is added to it again and it becomes 11. The increment adds 1 to myInt and it becomes 12. In the next iteration myInt is 12. 2 is added to it again and it becomes 14. The increment adds 1 to myint and it becomes 15.

After each iteration, the while condition is checked. At this point, that the while condition is checked, the myInt is 15, above 13, after 14 has been printed. The condition results in false, and the repetition of the block, stops.

while-loop

The syntax for the while-loop is:

    //initial statement here (initialization)
    while (condition) {
        //statements
        //cause for next iteration (continue Statement)
    }

The main difference between the do-while loop and the while-loop is, that for the while-loop, the condition is checked first, before the block is executed. With the do-while loop, the block is executed first, before the condition is checked. Note that the while-loop construct, does not end with a semicolon.

The following program repeats the first program above, but with a while-loop:

#include <stdio.h>

int main(int argc, char **argv) {
    int myInt = 0;
    while (myInt < 5) {
        printf("%d ", myInt);
        myInt++;
    }
    printf("\n");
    return 0;
}

The output is the same as for the first program above, that is:

0 1 2 3 4

The following program repeats the second program above, but with a while-loop:

#include <stdio.h>

int main(int argc, char **argv) {
    int myInt = 0;
    while (myInt < 13) {
        myInt = myInt + 2;
        printf("%d ", myInt);
        myInt++;
    }
    printf("\n");
    return 0;
}

The output is the same as for the second program above, that is:

2 5 8 11 14

for-loop

The syntax for the for-loop is:

#include <stdio.h>

int main(int argc, char **argv) {
    for (int myInt = 0; myInt < 5; myInt++) {
        printf("%d ", myInt);
    }
    printf("\n");
    return 0;
}

The block of the for-loop does not end with a semicolon. The output is the same as for the first program above, that is:

0 1 2 3 4

There is no semicolon after the increment statement (last statement) in the parentheses.

The following program repeats the second program above, but with a for-loop:

#include <stdio.h>

int main(int argc, char **argv) {
    for (int myInt = 0; myInt < 13; myInt++) {
        myInt = myInt + 2;
        printf("%d ", myInt);
    }
    printf("\n");
    return 0;
}

The output is the same as for the second program above, that is:

2 5 8 11 14

Conclusion

The do-while loop in C, repeats the execution of its block, as long as a condition is true. The do-while loop needs an initial statement (state), before the block. The do-while loop needs a cause-for-next-iteration (increment) statement, usually towards, the end of its block. The main difference between the do-while loop and the while-loop, is that, with the do-while loop, the block is always executed before the condition is checked; while with the while-loop, the condition is always checked before the block is executed. Both the do-while loop and the while-loop do essentially the same thing. The for-loop is a concise construct for the do-while loop or while-loop.

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 !

DEV Community: Chrysanthus

1.2 Time Complexity Explained in C

1. Time and Space Complexity in C

Constant Time - O(1)

Linear Time - O(n)

Logarithmic Time – O(log n)

Quadratic Time - O(n²)

n.log₂n Time

n + m Linear Time : O(n + m)

Nuance to do with ½n, 2n, etc.

Exponential Time Complexity : O(2ⁿ)

Factorial Time Complexity : O(n!)

Time limit

Approximation of Time Complexity

Exercise

Space Complexity

Conclusion

1.1 Looping in C

1. Time and Space Complexity in C

Do-while Loop Syntax

do-while Loop Example

while-loop

for-loop

Conclusion

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

O(N²) Solution