1. Longest Word Length (MCS)#

This question was about finding the length of the longest word in a given string.

int longest(char* sentence) {
    // maximum length of a word
    int max = 0;

    // current length of a word
    int length = 0;

    // iterate over the sentence
    for(int i = 0; sentence[i] != '\0'; i++){
        // if a space is found word end
        if(sentence[i] == ' '){
            // check if the current word length is greater than max
            max = length > max ? length : max;
            // reset the length
            length = 0;
        } else {
            // increment the length
            length ++;
        }
    }

    // check for the last word (since there is no space at the end)
    max = length > max ? length : max;
    
    // return the maximum length
    return max;
}

2. Grains (MCS)#

This question was about finding the sum of grains on the chessboard.

The first box had 1 grain. The second box had 2 grains. The third box had 4 grains. The fourth box had 8 grains. And so on.

Your task was to find the sum of grains up to the box number n.

Naive Solution

long grains(long square) {
    long sum = 0;

    for (int i = 1; i < square; i++) {
        // since pow returns a double 
        // typecast it to long
        sum += (long) pow(2, i);    
    }

    return sum;
}

A more optimized solution would be to use the formula 2^n - 1. (Why?)

long grains(long square) {
    return (long) pow(2, square) - 1;
}

An even more optimized solution would be to use bitwise operators.

long grains(long square) {
    return (1 << square) - 1;
}

3. Hamming (MCS)#

This was a fairly easy question. You were given two strings of equal length. And you had to find the number of places where the characters were different.

int hamming(char* dna1, char* dna2) {
    int diff = 0;
    
    // iterate over the strings
    // (you can also use strlen)
    for(int i = 0; dna1[i] != '\0'; i++) {
        // if characters are different
        // increment the difference count
        if (dna1[i] != dna2[i]) 
            diff++;
    }
    
    return diff;
}

4. RNA Transcription#

This was another “easier” question. Your task was to replace the DNA sequence with its corresponding RNA sequence.

In other words you just had to replace

• “G” with “C”
• “C” with “G”
• “T” with “A”
• and “A” with “U”

char* complement(char* dna) {
    // iterate over the string "dna"
    for(int i = 0; dna[i] != '\0'; i++){
        // you can use regular if-else
        // but switch is more readable
        switch(dna[i]){
            case 'G':
                dna[i] = 'C';
                break;
            case 'C':
                dna[i] = 'G';
                break;
            case 'T':
                dna[i] = 'A';
                break;
            case 'A':
                dna[i] = 'U';
                break;
        }
    }

    // return the modified dna string
    return dna;
}

5. Population Growth (MCS)#

This question is my personal favorite. Taken from the Harvard CS50 course.

You were given the initial population, the growth rate, and the target population. Your task was to find the number of years it would take for the population to reach the target population.

Every year

• the population grows by 1/3 of last year’s population
• and 1/4 of the (last year’s) population dies

That is

Growth = Last Year Population / 3

Deaths = Last Year Population / 4

Current Year Population = Last Year Population + Growth - Deaths

int growth(int start, int end) {
    int years = 0;
    
    while(start < end) {
        start += (start / 3) - (start / 4);
        years++;
    }
    
    return years;
}

Note to Python folks

The division is truncated. So in python 5/3 would give 1.6666666666666667 but in C it would give 1.

So in python you would have to use // for integer division.

1. Eliud’s Eggs#

This question was fairly simple (if you could understand what it wants).

TLDR it was about how many 1 bits are there in the binary representation of the number.

One way to solve it is to convert the number to binary and count the number of 1s. But that’s not efficient.

A more efficient way is to use bitwise operators.

In the below snippet we are using the bitwise AND operator & to check if the last bit is 1. If it is we increment the eggs count.

Then we discard the last bit by shifting the number to the right by 1. (This is equivalent to dividing the number by 2).

// eliud's eggs
int count(int display)
{
    int eggs = 0;

    // repeat till display != zero
    while (display)
    {
        // if last bit of display is 1
        if (display & 1)
            eggs++; // increment eggs

        // discard the last bit
        display >>= 1;
    }

    return eggs;
}

2. Luhn#

This was also a fairly easy question 😁. The twist was the input was not clean.

If you’ve read the problem statement, it said ignore the spaces, but reject any non digits.

Rest the algorithm was easy, just iterate the string backward, and keep a flag to check if the current digit is the second digit from the right.

bool valid(char *number)
{
    bool flag = false; // for checking every 2nd number
    int sum = 0;
    // reverse traverse string;
    for (int i = strlen(number) - 1; i >= 0; i--)
    {
        if ('0' <= number[i] && number[i] <= '9')
        {
            int digit = number[i] - '0';
            if (flag)
            {
                digit *= 2;
                sum += digit > 9 ? digit - 9 : digit;
            }
            else
            {
                sum += digit;
            }
            // reverse flag
            flag = !flag;
        }
        else if (number[i] == ' ')
        {
            // ignore spaces
            continue;
        }
        else
        {
            // no non digit character allowed
            return false;
        }
    }

    return sum % 10 == 0;
}

3. Matching Brackets (MCS)#

This was a classic Stack problem. Let the solution speak for itself.

bool valid(char *sequence)
{
    char stack[100] = {0}; // initialized a stack
    int top = -1;

    // iterate over string
    for (; *sequence != '\0'; sequence++)
    {
        switch (*sequence)
        {
        case '(':
        case '{':
        case '[':
            stack[++top] = *sequence;
            break;
        case ')':
            if (stack[top] == '(')
                top--;
            else
                return false;
            break;
        case '}':
            if (stack[top] == '{')
                top--;
            else
                return false;
            break;
        case ']':
            if (stack[top] == '[')
                top--;
            else
                return false;
            break;
        }
    }

    return top < 0; // is stack empty?
}

4. Sublist (MCS)#

This was another simp… okay, this was fairly hard TBH. If you’ve read the problem carefully, you would’ve recognized its the classic Substring problem (taught is Algorithms classes).

There are various optimal solution for this (KMP, Rabin Karp etc, you can look them up), but here I’ll be showing the bruteforce approach.

// hackerrank did a horrendous job naming the "size" variable of the lists in C
bool sublist(int a_count, int *a, int b_count, int *b)
{
    // if size of a is greater than b
    // then a can't be a sublist of b
    if (b_count < a_count)
        return false;

    // flag to check if a is sublist of b
    bool is_sublist = true;

    for (int i = 0; i <= b_count - a_count; i++)
    {
        // reset the flag for every iteration
        is_sublist = true;

        // check if a is equal to b[ i : i+ size of a]
        for (int j = 0; j < a_count; j++)
        {
            if (a[j] != b[i + j])
            {
                is_sublist = false;
                break;
            }
        }
        // if a is sublist of b
        // no need to check further
        if (is_sublist)
            return true;
    }

    return is_sublist;
}

5. Queen Attack (MCS)#

Back to geometry class.

Queen can attack if the lie in the same line vertically or horizontally. Or when they lie in the same diagonal.

Horizontal or vertical check is simple, just check if the x or y coordinates are same.

For diagonal check, the difference between the x and y coordinates should be same. (Why?.. Trigonometry 😁)

But!!! There’s a catch, the coordinates can only lie between 0 and 8. (Bet you didn’t see that coming).

bool can_attack(int q1_x, int q1_y, int q2_x, int q2_y)
{
    // coordinates can only lie between 0 and 8
    if (!(0 < q1_x && q1_x < 8) ||
        !(0 <= q1_y && q1_y <= 8) ||
        !(0 <= q2_x && q2_x <= 8) ||
        !(0 <= q2_y && q2_y <= 8))
        return false;

    // vertical and horizontal attack
    if ((q1_x == q2_x) || (q1_y == q2_y))
        return true;

    // lateral attack
    return abs(q1_x - q2_x) == abs(q1_y - q2_y);
}

6. Largest Series Product#

To the Sliding Window.

We start with a “window” containing 0 elements. We keep adding elements to the window until the window size is equal to the given span.

Next we calculate the product of the elements in the window and compare it with the maximum product found so far.

Then we remove the first element from the window and repeat the process.

(Might need a youtube video to explain this 😅, look it up)

int largest_product(char *digits, int span)
{
    // If span is 0 just return 1
    // Why (The same why 0! = 1)
    if (span == 0)
        return 1;

    // maximum product found
    int max_product = 0;

    // first and last index of window
    int first = 0, last = 0;
    // current window product
    int current = 1;

    while (last < strlen(digits))
    {
        int digit = digits[last] - '0';
        last++;

        if (digit == 0)
        {
            first = last;
            current = 1;
        }
        else
        {
            current *= digit;
            // if current window size == span
            if (last - first == span)
            {
                max_product = max_product > current ? max_product : current;
                // remove the first element from the product
                current /= digits[first] - '0';
                first++;
            }
        }
    }

    return max_product;
}

This was the first edition of the Monthly Coding Series 2025. We hope you had a great time participating in the event. Stay tuned for the next edition.