Problem Statement#

Given the position of two queens on a chess board, indicate whether or not they are positioned so that they can attack each other.

In the game of chess, a queen can attack pieces which are on the same row, column, or diagonal.

A chessboard can be represented by an 8 by 8 array.

So if you are told the white queen is at c5 (zero-indexed at column 2, row 3) and the black queen at f2 (zero-indexed at column 5, row 6), then you know that the set-up is like so:

You are also able to answer whether the queens can attack each other. In this case, that answer would be yes, they can, because both pieces share a diagonal.

Explanation#

To determine if two queens can attack each other, we need to check the following conditions:

1. If they are on the same row (i.e., their x-coordinates are equal).
2. If they are on the same column (i.e., their y-coordinates are equal).
3. If they are on the same diagonal (i.e., the absolute difference between their x-coordinates is equal to the absolute difference between their y-coordinates).

bool can_attack (int q1_x, int q1_y, int q2_x, int q2_y) {
    // Check if queens are on the same row or column
    if (q1_x == q2_x || q1_y == q2_y) {
        return true;
    }
    // Check if queens are on the same diagonal
    if (abs(q1_x - q2_x) == abs(q1_y - q2_y)) {
        return true;
    }
    return false;    
}

Problem Statement#

 _ _ _ _ _ _ _
|E| |E|E| | |E|

 _ _ _ _ _ _ _
|1|0|1|1|0|0|1|

 _ _ _ _ _ _ _
| | | |E| | | |

 _ _ _ _ _ _ _
|0|0|0|1|0|0|0|

Solution#

To count the number of 1 bits in the binary representation of a number, we can use a simple loop to check each bit of the number. We can do this by repeatedly checking the least significant bit (LSB) and then right-shifting the number until it becomes zero.

Division approach

int count_eggs (int display) {
    int count = 0;
    while (display > 0) {
        // Check if the remainder is 1
        if (display % 2) {
            count++;
        }
        // Remove the least significant bit
        display /= 2;
    }
    return count; 
}

Bitwise approach

int count_eggs (int display) {
    int count = 0;
    while (display > 0) {
        // Check if the least significant bit is 1
        if (display & 1) {
            count++;
        }
        // Right shift the number to check the next bit
        display >>= 1;
    }
    return count; 
}

Problem statement#

A number is ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return true if n is an ugly number.

Solution#

To determine if a number is an ugly number, we can repeatedly divide the number by 2, 3, and 5 until it becomes 1 or cannot be divided further. If the final result is 1, then the number is an ugly number.

#include <stdio.h>

int main(){
    int num;
    scanf("%d", &num);

    while(num % 2 == 0) {
        num /= 2;
    }
    while(num % 3 == 0) {
        num /= 3;
    }
    while(num % 5 == 0) {
        num /= 5;
    }

    if(num == 1) {
        printf("true\n");
    } else {
        printf("false\n");
    }
}

Problem statement#

WAP to find sum of digits of a number until sum becomes single digit.

Input : 1234

Output : 1

Explanation:

The sum of 1 + 2 + 3 + 4 = 10 (two digit)

Hence ans will be 1 + 0 = 1

Solution#

int sumofdigit (int n) 
{
    int sum;
    
    do {
        sum = 0;
        while (n > 0) {
            sum += n % 10; // Add the last digit to sum
            n /= 10; // Remove the last digit
        }
        n = sum; // Update n to the sum of digits
    } while (n > 9); // Repeat until sum is a single digit

    return sum;
}

Problem statement#

Solution#

To calculate the age on a specific planet, we first convert the given seconds into Earth years. Then, we divide that by the planet’s orbital period in Earth years to get the age on that planet.

double space_age (char* planet, int seconds) {
    double earth_years = seconds / 31557600.0; // Convert seconds to Earth years
    
    if (strcmp(planet, "Mercury") == 0) {
        return earth_years / 0.2408467; // Mercury's orbital period
    } else if (strcmp(planet, "Venus") == 0) {
        return earth_years / 0.61519726; // Venus's orbital period
    } else if (strcmp(planet, "Earth") == 0) {
        return earth_years; // Earth
    } else if (strcmp(planet, "Mars") == 0) {
        return earth_years / 1.8808158; // Mars's orbital period
    } else if (strcmp(planet, "Jupiter") == 0) {
        return earth_years / 11.862615; // Jupiter's orbital period
    } else if (strcmp(planet, "Saturn") == 0) {
        return earth_years / 29.447498; // Saturn's orbital period
    } else if (strcmp(planet, "Uranus") == 0) {
        return earth_years / 84.016846; // Uranus's orbital period
    } else if (strcmp(planet, "Neptune") == 0) {
        return earth_years / 164.79132; // Neptune's orbital period
    }

    return -1; // Invalid planet name
}

Problem statement#

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Input Format:

• An integer value n representing size of the array
• Next line contains n space separated integer values of the array.

Solution#

Video Explanation

int max_profit (int* stocks, int days) {
    int profit = 0;
    for (int i = 1; i < days; i++) {
        if (stocks[i] > stocks[i-1]) {
            profit += stocks[i] - stocks[i-1];
        }
    }
    return profit;
}

Problem statement#

Given a string s, find the length of the longest substring without repeating characters.

Input Format:-

Only one line that contains the string.

Output Format:-

Print te length of longest substring without repeating characters.

Constraint:-

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

Solution#

To find the length of the longest substring without repeating characters, we can use a sliding window approach with a map to keep track of the last known index of each character.

We will maintain two pointers, start and end, to represent the current substring. As we iterate through the string, we will update the start pointer whenever we encounter a repeating character.

We will also keep track of the maximum length of the substring found so far.

#define max(x, y) x > y ? x : y

int last_known_index[256];

int longest_substring (char* input) {
    // reset the last known index map
    for (int i = 0; i < 256; i++) {
        last_known_index[i] = -1;
    }

    int start = 0;
    int end = 0;
    int longest = 0;

    while (input[end] != '\0') {
        char c = input[end];

        if (last_known_index[c] >= start) {
            longest = max(longest, end - start);
            start = last_known_index[c] + 1;
        }

        last_known_index[c] = end;
        end++;
    }

    return max(longest, end - start);
}

Problem statement#

Given a string, your task is to determine the longest palindromic substring of the string. For example, the longest palindrome in aybabtu is bab.

Input

The only input line contains a string of length n. Each character is one of a-z.

Output

Print the longest palindrome in the string. If there are several solutions, you may print any of them.

Constraints

$1 ≤ n ≤ 10^6$

Solution#

Video Explanation

#include <string.h>

char* longest_palindrome (char* input) {
    int n = strlen(input);
    if (n == 0) return "";

    int start = 0, max_length = 1;

    for (int i = 0; i < n; i++) {
        // Check for odd length palindromes
        int left = i, right = i;
        while (left >= 0 && right < n && input[left] == input[right]) {
            if (right - left + 1 > max_length) {
                start = left;
                max_length = right - left + 1;
            }
            left--;
            right++;
        }

        // Check for even length palindromes
        left = i, right = i + 1;
        while (left >= 0 && right < n && input[left] == input[right]) {
            if (right - left + 1 > max_length) {
                start = left;
                max_length = right - left + 1;
            }
            left--;
            right++;
        }
    }

    // Extract the longest palindrome substring
    char* result = (char*)calloc((max_length + 1), sizeof(char));
    strncpy(result, &input[start], max_length);
    return result;
}

Problem statement#

Given a string and a pattern, your task is to count the number of positions where the pattern occurs in the string.

Input

The first input line has a string of length n, and the second input line has a pattern of length m. Both of them consist of characters a-z.

Output

Print one integer: the number of occurrences.

Constraints

$1 ≤ n,m ≤ 10^6$

Solution#

Naive String Matching Algorithm

#include<string.h>

int substring_count (char* input, char* pattern) {
    // Naive string matching
    int n_input = strlen(input);
    int n_pattern = strlen(pattern);
    int count = 0;

    for (int i = 0; i < n_input - n_pattern + 1; i++) {
        if(strncmp(input + i, pattern, n_pattern) == 0){
            count++;
        }
    }
    return count;
}

Improvements -

• KMP Algorithm
• Rabin-Karp Algorithm
• Z Algorithm

Problem statement#

Items: [
  { "weight": 5, "value": 10 },
  { "weight": 4, "value": 40 },
  { "weight": 6, "value": 30 },
  { "weight": 4, "value": 50 }
]

Solution#

Video Explanation

#define max(x, y) x > y ? x : y

#define WEIGHT 0
#define VALUE 1

// Function to allocate a 2D matrix
int** alloc_matrix(int rows, int cols) {
    int** matrix = (int**) calloc(rows, sizeof(int*));
    for (int row = 0; row < rows; row ++){
        matrix[row] = (int*) calloc(cols, sizeof(int)); 
    }
    return matrix;
}

// Function to free a 2D matrix
void free_matrix(int** matrix, int rows){
    for (int row = 0; row < rows; row ++){
        free(matrix[row]); 
    }
    free(matrix);
}


int kanpsack (int n_item, int n_property, int** items, int capacity) {
    // Initialize a matrix of 
    // rows: items + 1 
    // columns: knapsack capacity + 1 
    int** matrix = alloc_matrix(n_item + 1, capacity + 1);

    for (int item = 0; item < n_item; item++) {
        for(int weight = 1; weight <= capacity; weight++) {
            
            int item_weight = items[item][WEIGHT];
            int item_value = items[item][VALUE];
            

            // Maximum value while exluding current item
            int exclude_value = max(matrix[item+1][weight-1], matrix[item][weight]);

            // current item cannot fit in current weight
            if (items[item][WEIGHT] > weight) {
                matrix[item + 1][weight] = exclude_value;
            } 
            // current item can fit in current weight
            else {
                // Value when including current item
                int include_value = item_value + matrix[item][weight-item_weight];
                
                // Maximum value for current weight
                matrix[item + 1][weight] = max(include_value, exclude_value);
            }
        }
    }

    // Max value is the last cell
    int max_value = matrix[n_item][capacity];
    // Free the allocated matrix
    free_matrix(matrix, n_item + 1);
    // Return the maximum value
    return max_value;
}

Problem statement#

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ways you can produce a money sum x using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 8 ways:

• 2+2+5
• 2+5+2
• 5+2+2
• 3+3+3
• 2+2+2+3
• 2+2+3+2
• 2+3+2+2
• 3+2+2+2

Input

The first input line has two integers n and x: the number of coins and the desired sum of money.

The second line has n distinct integers $c_1$,$c_2$,…,$c_n$: the value of each coin.

Output

Print one integer: the number of ways modulo $10^9+7$.

Constraints

$1 ≤ n ≤ 100$

$1 ≤ x ≤ 10^6$

$1 ≤ c_i ≤ 10^6$

Solution#

Video Explanation

const int MOD = 1e9 + 7;

int ways (int n_coin, int amount, int* coins) {
    int* dp = (int *) calloc(amount+1, sizeof(int));

    dp[0] = 1;

    for(int current_amount = 1; current_amount <= amount; current_amount++){
        for(int coin = 0; coin < n_coin; coin++) {
            if(current_amount - coins[coin] >= 0) {
                dp[current_amount] = (dp[current_amount] + dp[current_amount - coins[coin]]) % MOD;
            }
        }
    }

    int ans = dp[amount];
    free(dp);
    return ans;
}