DEV Community: Chrysanthus

2.2 Compute number of integers divisible by k in range a..b in C. Your ultimate solution should give the result in O(1) time.

Chrysanthus — Fri, 03 Jul 2026 03:41:17 +0000

2 Basic Algorithm Problems 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.

Problem in Detail

Write a function:

    int solution(int A, int B, int K);

For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.

Write an efficient algorithm for the following assumptions:

        A and B are integers within the range [0..2,000,000,000];
        K is an integer within the range [1..2,000,000,000];
        A ≤ B.

Note:
The left limit is A and the right limit is B, indicated by [A..B]. Both limit integers are included as possible required dividends. ‘A’ may or may not be divisible by K. B may or may not be divisible by K. The integers in between, may or may not be divisible by K.

Brute Force Approach

The brute force approach test all the integers from ‘A’ to B (inclusive). This takes O(n) time complexity (from A to B, inclusive). In this situation, O(n) is almost O(B - A). Precisely, O(n) = O(B - A +1). The +1 is because of both inclusive limits, when A is divisible by K and B is divisible by K. To know if an integer is divisible by K, use the modulus operator, %. If the remainder is 0, then it is divisible by K. The brute force approach program is:

#include <stdio.h> 

int solution(int A, int B, int K) {
    int num = 0;
    for (int i=A; i<=B; i++) {
        if (i%K == 0)
            num += 1;    // same as num = num + 1
    }

    return num;
}

int main() 
{ 
    int ret = solution(6, 11, 2);

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

    return 0; 
}

The scoring and detected time complexity for this brute force approach is:

    Task score : 50% -  Correctness : 100% ; Performance : 0%
    Detected time complexity: O(B-A), same as O(n), where n is B - A, though n is actually B-A+1.

This approach takes O(n) time complexity (from A to B, inclusive).

Smart Approach

There are two situations here: the situation where A is divisible by K and the situation where A is not divisible by K.

When A is Divisible by K

K is less than Or Equal to (B - A)

Summing K as an interval, from A to B is the same as summing K as an interval from 0 to (B - A), beginning from the first divisible integer.

Under this condition, the number of intervals of K in the range [A..B], is the same as the number of intervals in the range 0 to (B - A), beginning from 0. That is, the range (B - A) has been translated down to begin at zero. Since A is divisible by K, under this condition, it means that 0 has to be considered as divisible by K.

Using the above sample case, (11 - 6) = 5 and K = 2. From 0 to 5, intervals of 2 occurs 2 times, from 2 to 4. That is, 0 + 2 = 2 and 2 + 2 = 4. From 6 to 11, 6 is divisible by 2. Adding 2 to 6 is 8; and 8 is divisible by 2. Adding 2 to 8 is 10; and 10 is divisible by 2. This makes a count of 3, for number of integers divisible by 2, from 6 to 11, inclusive. However, there are only two intervals of 2, in both corresponding ranges. Since 6 in the range, [6..11] is divisible by 2, then 0 in the range [0..5] has to be considered as divisible by 2, to make the count 3, from 0 to 5, instead of 2, in the range, 0 to (B - A), inclusive.

So, the number of required dividends, is obtained from the integer division,

    (B - A)/k +1

where (B - A)/k is the number of full intervals, and +1 accounts for the A divisible by K (corresponding to 0 divisible by K). With the sample case given,

    (11 - 6)/2 + 1 = 5/2 + 1 = 2½ +1 = 2 + 1 = 3

Integer division truncates (off) any fraction, even if the fraction is greater than ½ (making 2½ as 2). Again, the addition of 1, accounts for A (or 0), if A from [A..B] is divisible by K.

There is trouble! The problem is, in C, "(B - A)/k +1" as integer division, does not give the right answer all the times, for different test cases, because of the way integer division is done in C. Since the floating number division of (B - A)/k is the same as B/K + A/K, mathematically, then the solution in C, is to use the following integer divisions plus 1:

    B/K - A/K + 1

where B/K and A/K are C integer divisions with truncation.

Situation where K is greater than (B - A) but Less than Or Equal to A, and A is divisible by K

In this case, it is not possible to have more than zero interval of K from A to B (inclusive). In this situation, it is only possible to have at most one divisible dividend from A to B (inclusive), which is just A.

Consider the case, where A = 10, B = 14 and K = 5: B - A = 14 - 10 = 4, and K = 5 is greater than 4. The only possible dividend here, is 10 = A, as 10 / 5 = 2 remainder 0. Substituting into the above formula gives,

    B/K - A/K + 1 = 14/5 - 10/5 + 1 = [2 + 4/5] - [2 + 0] + 1

With integer division, the fraction, 4/5 is ignored, leading to, 2 - 2 + 1 = 0 + 1 = 1 , and correct.

When A is not Divisible by K

K is less than Or Equal to (B - A)

Consider another sample case, where K=10, A = 16 and B = 53. A (16) is not divisible by 10. 20 is divisible by 10. 20 is the first required dividend, in the range 16 to 53 (inclusive). 20 + 10 = 30 is divisible by 10. 30 is the second required dividend. 30 + 10 = 40 is divisible by 10. 40 is the third required dividend. 40 + 10 = 50 is divisible by 10. 50 is the fourth required dividend. 50 + 10 = 60, which crosses the range. B (53) is not divisible by 10. The number of integers in the range, [16..53] that are divisible by 10 is 4.

The integer division,

    (B - A)/k

where (B - A)/k is the number of intervals (without +1), in the range, A to B (inclusive), should be considered here. With the current sample case,

    (53 - 16)/10 = 37/10 = [3 +7/10] = 3,

since integer division in C will truncate off the fraction, 7/10. Three appears here as the number of intervals from the first required dividend. The actual number of required dividends in the range, 16 to 53 (inclusive), is 4, as determined above. Something is wrong! What about the C integer division of 53/10 - 16/10 ? That gives:

    53/10 - 16/10 = [5 + 3/10] - [1 + 6/10] = 5 - 1 = 4, the correct answer

as integer division in C will truncate off the fractions, 3/10 and 6/10. The reader should accept that, when A is not divisible by K, and K is less than or equal to (B - A), the C integer division formula of

    B/K - A/K

gives the correct answer (number of dividends). Since A or its corresponding 0 is not divisible by K here, 1 is not added to the expression.

Situation where K is greater than (B - A), and less than or equal to B, but A is not divisible by K

In this case, it is not possible to have more than zero interval of K from A to B (inclusive). In this situation, it is only possible to have at most one divisible dividend from A to B (inclusive).

Consider another sample case, where K=10, A = 46 and B = 53. B - A = 53 - 46 = 7. There is only one number from 46 to 53 (inclusive), that is divisible by 10, and that number is 50. Using the formula, B/K - A/K, gives

    53/10 - 46/10 = [5 + 3/10] - [4 + 6/10] = 5 - 4 = 1, and correct.

The fraction, 3/10 and 4/10 are truncated off by C integer division. The reader should accept that, when A is not divisible by K and K is greater than (B - A), but less than or equal to B, the C integer division formula of

    B/K - A/K

gives the correct answer (number of dividends). With K = 20 and A = 46 with B = 53, no integer in the range, [A..B] = [46..53] is divisible by 20 and the formula gives the correct answer with,

    53/20 - 46/20 = [2 + 13/20] - [2 + 6/20] = 2 - 2 = 0

Situation of K being greater than B

If K is greater than B, then no integer in the range, A to B (inclusive), would be divisible by K. This is not a condition to take into consideration.

The Two Situations Combined using Pseudo-Code:

    if (A is divisible by K)
        answer =  B/K - A/K + 1    //C integer division
    else
        answer =  B/K - A/K    //C integer division

If the else-part is not coded, then it has to be replaced by a return statement. The smart program is:

#include <stdio.h> 

int solution(int A, int B, int K) {
    if (A%K == 0) 
        return B/K - A/K + 1;

    return B/K - A/K;
}

int main() 
{ 
    int ret = solution(6, 11, 2);
    printf("%i\n", ret);

    return 0; 
}

The output is 3. In the if-compound statement, only either the if-part is executed or the else part is executed. So only one operation takes place for the solution() function. The scoring and detected time complexity for this smart approach is:

Detected time complexity: constant time, O(1)
Task score : 100% - Correctness : 100% ; Performance : 100%

Conclusion

The idea of summing, is that K, as an interval, has to be added repeatedly, until the sum reaches B or is close to B, beginning from the first possible dividend number. This is the same as adding K as an interval from 0 to (B - A), until the sum reaches (B - A), or is close to (B - A), beginning from the first possible division number. All that is when K is less than or equal to (B - A). When K lies between (B – A) and A, after B, or within A and B, there may be only one dividend and zero intervals of K.

The pseudo code is:

    if (A is divisible by K)
        answer =  B/K - A/K + 1    //C integer division
    else
        answer =  B/K - A/K    //C integer division

Thanks for Reading and More to Read:

2.2 Compute number of integers divisible by k in range a..b in C++. Your ultimate solution should give the result in O(1) time.

2.1 Count minimal number of jumps from position X to Y in C. Your ultimate solution should give the result in O(1) time.

Chrysanthus — Thu, 02 Jul 2026 10:45:48 +0000

2 Basic Algorithm Problems 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.

Basic Algorithm in this full course refers to algorithms that do not really fall under any particular algorithm heading. This tutorial is the first of such problems.

Problem in Detail

A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D.

Count the minimal number of jumps that the small frog must perform to reach its target.

Write a function:

    int solution(int X, int Y, int D);

that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.

For example, given:

  X = 10
  Y = 85
  D = 30

the function should return 3, because the frog will be positioned as follows:

        after the first jump, at position 10 + 30 = 40
        after the second jump, at position 10 + 30 + 30 = 70
        after the third jump, at position 10 + 30 + 30 + 30 = 100

Write an efficient algorithm for the following assumptions:
X, Y and D are integers within the range [1..1,000,000,000];
X <= Y.

Note:
This problem can be solved in O(n) time complexity or O(1) time complexity. The explanation below begins with O(n) time. After that O(1) time is explained.

The "catch" for this problem is to be able to produce a O(1) time complexity instead of producing a O(n) time complexity for the number of intervals.

O(n) Time

The function for O(n) time is:

    int solution(int X, int Y, int D) {
        int ctr = 0;    //counter
        int sum = X;
        for (int i=0; sum < Y; i++) {
            sum = sum + D;
            ++ctr;
        }
        return ctr;
    }

Note that the while condition is (sum < Y), which is the opposite of (sum >= Y), and correct.

The score for this function is:

    Total Score : 55%
    Correctness : 100%
    Performance : 20%

This means that the function will always give the correct minimal number of jumps, but gets slower and slower, as the value of D gets smaller and smaller (or as the value of Y gets bigger and bigger, or both).

The function begins by considering the value of X as the initial total distance covered. The distance covered while the frog is jumping, is held in the variable, sum. The for-loop keeps adding the value of D to sum, while checking if the sum is equal to Y or above, and counting the number of jumps.

Note that the for-loop executes its body first before verifying if the while-condition is true. That is why the while-condition in the parentheses is (sum < Y) and not (sum <= Y). It is also because the counter is initialized to 0.

The time complexity for the above function is, O(Y-X). This is effectively O(difference), where difference is at least the distance from X to Y, and means n approximately, giving O(n) time complexity.

O(1) Time

In the question illustration, each time the frog jumps 30 units, a count of 1 is added. The frog finally makes 3 jumps, exceeding 85 units to 100 units, at the last jump. X, Y and D are each an integer.

Now, X = 10. If Y was 100, then (100 – 10) divided by 30 would have given 3, with no remainder. That is 100 – 10 = 90 / 30 = 3 R 0. Here D = 30.

However, Y = 85. (85 – 10 ) divided by 30 gives, 2 remainder 15. That is, 85 – 10 = 75 / 30 = 2 R 15 . In order to obtain 3, 1 has to be added to 2 (result of integer division), to give 3 .

So, if the difference between Y and X divided by the fixed distance D, has no remainder (R = 0), then the quotient is the number of jumps. If there is a remainder, independent of the value of the remainder, it means that one interval (fixed) distance still has to be covered; and so 1 has to be added to the whole number part of the quotient, to obtain the number of jumps.

So, to obtain the number of jumps, either of two formulas has to be used. That is, either

    (Y - X )  / D = N R 0,  // N taken

OR

    (Y - X )  / D = N R > 0,  //N + 1 taken

And so, for any set of arguments, for parameters X, Y and D, one of the two formulas (not both) has to be executed. That is constant time, which is same as O(1) time.

The constant time function (program) is:

    #include <stdio.h> 

    int solution(int X, int Y, int D) {  
            if ((Y - X)%D == 0)
                return (Y - X)/D;
            else
                return (Y - X)/D + 1;
    }

    int main() 
    { 
        int ans = solution(10, 85, 30);
        printf("%i\n", ans);

        return 0; 
    }

The output is 3, for the given set of arguments, (10, 85, 30). Either the formula, "(Y – X)/D" or "(Y - X)/D + 1" is executed as one operation, for each set of arguments (one pass through the function), and that results in the time complexity, O(1).

The score for the solution() function here, is:

    Task score : 100% -  Correctness : 100% ; Performance : 100%
    Detected time complexity : O(1)

Conclusion

To count the number of jumps in this problem or a similar problem, in constant time, use the formula, which is to subtract the start distance from the end distance, and then divide by the interval (fixed) distance. If the remainder is 0, then the quotient is the answer. If the remainder is not 0, it means that one interval distance still has to be covered; and so 1 has to be added to the whole number part of the quotient, to obtained the answer.

Thanks for Reading and More to Read:

2.1 Count minimal number of jumps from position X to Y in C++. Your ultimate solution should give the result in O(1) time.

1.3 Space Complexity Explained in C

Chrysanthus — Wed, 01 Jul 2026 12:29:30 +0000

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.

The estimate of space complexity is the same, as with time complexity, using big-O notation. However, n in space complexity refers to number of memory locations. An input of one variable, is O(1) space complexity. An array input of n locations is O(n) space complexity. A two-dimentional array of size n² is O(n²) space complexity. A three-dimentional array of size n³ is O(n³) space complexity; and so on. However space complexity is not limited to only the input. It also involves auxiliary space.

Auxiliary Space is space needed by the algorithm beyond the input space, in other to function. Temporary space is also auxiliary space.

Space Complexity of an algorithm is defined as the total space taken up by the algorithm with respect to the input size. The big-O notation gives the estimate.

Space complexity consists of both auxiliary space and space used by input.

Unfortunately many documents give just the auxiliary space for space complexity without the input space. That is not strictly correct.

The rest of the sections in this tutorial, will be similar to their counterparts in the previous time-complexity tutorial.

Constant Space - O(1)

Consider the following program:

    #include <stdio.h>

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

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

        return 0;
    }

The output is 6. The space complexity is O(1) for the single variable, result. This involves only the auxiliary space. There is no input space: the calling function sends no argument.

Linear Space - O(n)

Consider the following program:

    #include <stdio.h>

    void solution(int arr[]) {
        int arrA[] = {arr[0], arr[1], arr[2], arr[3], arr[4]};
        printf("%i %i %i %i %i", arrA[0], arrA[1], arrA[2], arrA[3], arrA[4]);
        printf("\n");
    }

    int main(int argc, char **argv)
    {
        int arry[] = {1, 2, 3, 4, 5};
        solution(arry);

        return 0;
    }

The output is:

    1 2 3 4 5

Strictly speaking, the space complexity in this program is O(2n); that is, O(n) for the input array, arry and O(n) for the array, arrA in the algorithm (function). However, the coefficient which is the multiple of the space complexity expression, is usually omitted when quoting the space complexity. So, the space complexity for the above problem is:

    O(n)

which ends up just referring to the auxiliary space. Do not forget that the array, arry is different from the array, arrA, while the array, arry is the same as the array arr (in the parameter parentheses – they have the same start reference variables).

Logarithmic Space – 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 or space 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 space, O(log n) is usually less than half the linear space, O(n), e.g 3 is less than half of 8, which is 4.

For code example of logarithmic space, with the number 8 as the upper limit, consider the following program:

    #include <stdio.h>

    void solution(int z) {
        int b = z;
        int c = 2;
        int d = 3;

        printf("%i %i %i", b, c, d);
        printf("\n");
    }

    int main(int argc, char **argv)
    {
        int a = 1;
        solution(a);

        return 0;
    }

The output is:

     1 2 3

The space complexity is actually,

    O(4) = O(log₂n)

out of an assumed 8 expected locations, by the user. Many documents will give the space complexity here as,

    O(3) = O(log₂n)

referring to the auxiliary space only, without the input space. The input space complexity is O(1), for the single variable, "int a = 1;".

Quadratic Space - 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 program:

    #include <stdio.h>

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

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

        return 0;
    }

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

There is no input and so no input space. The auxiliary space and the total space complexity is:

O(64) =  O(8²) = O(n²)

which comes from the 2D array and not from the printf statement.

n.log₂n Space

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 log₂ 8 = 3;
∴ n x log₂n = 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) space 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 program:

    #include <stdio.h>

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

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

        return 0;
    }

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 is no input and so no input space. The auxiliary space and total space complexity is:

    O(3 x 8) = O(24) = O(3 x 2³) = O(n.log₂n)

which comes from the 2D array and not from the printf statement.

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

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

    #include <stdio.h>

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

        printf("\n");

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

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

        return 0;
    }

The output is:

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

There is no input and so no input space. The auxiliary space and total space complexity is:

    O(7+9) = O(n+m)

which comes from the 2D array and not from the printf statement. The contribution of the memory location of the start variable, in the solution function, is ignored.

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

    #include <stdio.h>

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

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

        return 0;
    }

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 space), 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 space complexity expressions are avoided.

Approximation of Space Complexity

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

Exercise

Problem 1:
You are given an integer n. Count the total of 1 + 2 + . . . + n, in O(n²) time. Also give the space complexity in big-O notation.

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.

The input space complexity is O(1) for the variable, "int n = 4;" . The auxiliary space complexity is also just O(1), for the variable, "int result = 0;" . The nested for-loop uses only this variable. Any extra temporary variable needed by the algorithm function, is ignored in this case. Strictly speaking, the space complexity should be given as:

    O(2 x 1)

for both the input space and auxiliary space. However, conventionally, it is given as:
O(1)

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.

The space complexity for this program is still given as:

    O(1)

which is not strictly correct.

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.

The space complexity for this program is still given as:

    O(1)

which is not strictly correct. It cannot be given as O(10) = O(n), because the number of obvious identifiable memory locations, is not up to 10.

Space Complexity in General

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.

Conclusion

Space Complexity of an algorithm is defined as the total space taken up by the algorithm with respect to the input size. The big-O notation gives the estimate.

Thanks for Reading and More to Read:

1.3 Space Complexity Explained in C++

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³

The second mathematical statement above, can be rewritten as:

        log₂ 8 = 3

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

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.

Thanks for Reading and More to Read:

1.2 Time Complexity Explained in C++

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.

Thanks for Reading and More to Read:

1.1 Looping in C++

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

DEV Community: Chrysanthus

2.2 Compute number of integers divisible by k in range a..b in C. Your ultimate solution should give the result in O(1) time.

2 Basic Algorithm Problems in C

Problem in Detail

Brute Force Approach

Smart Approach

Conclusion

Thanks for Reading and More to Read:

2.1 Count minimal number of jumps from position X to Y in C. Your ultimate solution should give the result in O(1) time.

2 Basic Algorithm Problems in C

Problem in Detail

O(n) Time

O(1) Time

Conclusion

Thanks for Reading and More to Read:

1.3 Space Complexity Explained in C

Time and Space Complexity in C

Constant Space - O(1)

Linear Space - O(n)

Logarithmic Space – O(log n)

Quadratic Space - O(n²)

n.log₂n Space

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

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

Approximation of Space Complexity

Exercise

Space Complexity in General

Conclusion

Thanks for Reading and More to Read:

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

Thanks for Reading and More to Read:

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

Thanks for Reading and More to Read:

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