Math, Implementation

In this problem, it is given that Yashvi has x number of chocolates and Femina has y number of chocolates. The total number of children is n. To distribute the chocolates among the children, it is necessary for the total number of chocolates to be more than or equal to the number of children. Because by doing so, it is guaranteed that every child will have atleast one chocolate. So the answer is YES only if the sum of x and y is greater than or equal to number of children. Otherwise the answer is NO

#include <stdio.h>

int main() {
    int x, y, n;

    // Input number of chocolates of type x and y
    scanf("%d %d", &x, &y);

    // Input number of children
    scanf("%d", &n);

    // Check if total chocolates are enough for all children
    if ((x + y) >= n) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }

    return 0;
}

Math, Implementation

The lock opens with the maximum digit of a given number. We extract each and every digit of the number by doing modulo 10 operation and then divide the number by 10 to discard the last digit. Then we take the maximum of all the digits and print the answer.

Instead of taking the number as an integer, you can take it as a string (or a character array). That way, each digit of the number is stored as a character, and you can easily loop through all characters to find the maximum digit — just like finding the maximum element in a normal array.

#include <stdio.h>

int main() {
    int t;
    scanf("%d", &t); // taking the number of test cases

    while (t--) { // loop runs for each test case
        long long n;
        scanf("%lld", &n); // input number for the current test case

        int maxi = 0;
        while (n > 0) {
            int rem = n % 10; // extract last digit
            if (rem > maxi) {
                maxi = rem; // update maximum digit
            }
            n /= 10; // remove last digit
        }
        printf("%d\n", maxi); // print maximum digit
    }
    return 0;
}

#include <stdio.h>
#include <string.h>

int main() {
    char num[100];
    scanf("%s", num);  // take number as a string

    char maxDigit = '0';

    for (int i = 0; i < strlen(num); i++) {
        if (num[i] > maxDigit)
            maxDigit = num[i]; // update maxDigit if current one is larger
    }

    printf("%c\n", maxDigit);
    return 0;
}

Array, Implementation, Brute Force

In this question, we are told to find the first non negative missing number in the array. To do this, as the constraints are very low, we can run a for loop from 0 to 100 and for every number, we can check whether it occurs in the array or not. If the number does not occur in the array, we finally print the number and move on. So, this problem requires the use of nested for loops.

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);  // Read the size of the array
    
    int a[n];  // Declare an array of size n
    
    // Read the array elements
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    
    // Check for the smallest missing number in range 0 to 100
    for (int i = 0; i <= 100; i++) {
        int found = 0;  // Flag to check if current number i exists in array
        
        // Search for current number i in the array
        for (int j = 0; j < n; j++) {
            if (a[j] == i) {
                found = 1;  // Number found in array
                break;      // No need to check further
            }
        }
        
        // If number i is not found in the array
        if (!found) {
            printf("%d\n", i);  // Print the missing number
            return 0;           // Exit the program
        }
    }
    
    return 0;
}

Array, Implementation, Hashing

As in the continuation of the previous question, if we paste the same code here, we will get a time limit exceeded error, due to tough constraints. So, we need to optimize our code to tailor the needs of this question. We will maintain a hash array of size n+1 initialized to -1 for all elements, where n is the size of the array. While traversing in the array, if we encounter a number less than or equal to n, we mark its presence in the hash array, if the number is greater than n, then we discard it due to pigeonhole principle. Finally, we initialize our answer variable by n+1, and traverse through the hash array, if the value at any particular index is -1, then we print the value and not see ahead. This will be our final answer.

#include <stdio.h>

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

    int a[n];
    int present[100002] = {0};  // Array to mark which numbers exist

    // Read array and mark present numbers
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if(a[i] < 100001) {
            present[a[i]] = 1;
        }
    }

    // Find the smallest number not present in the array (MEX)
    int mex = 0;
    while (present[mex]) {
        mex++;
    }

    printf("%d\n", mex);  // Print MEX
    return 0;
}

2D-Array, Math, Implementation

n is the number of rows, m is the number of columns In this problem, if we apply the general solution using a 2-D array, it will give memory limit exceeded error. To optimize, we first find out the row and column in which Mahek is seated. The row can be found out by the formula i = ((s-1) / m) + 1, and the column can be found out by the formula j = ((s-1) % m) + 1. Then, for each invigilator, we check whether Mahek's seat number is in their range or not by checking whether i >= r1 and i <= r2 and j >= c1 and j <= c2. Similarly for the second invigilator. If any one of these conditions become true, we print NO, else we print YES.

#include <stdio.h>

int main() {
    int s, n, m;

    // Read Mahek's seat number, rows, and columns
    scanf("%d %d %d", &s, &n, &m);

    // Calculate Mahek's seat position (row and column)
    // Seat numbering is row-wise starting from 1
    int mahek_row = (s — 1) / m + 1;
    int mahek_col = (s — 1) % m + 1;

    // Read first invigilator's region
    int r1, c1, r2, c2;
    scanf("%d %d %d %d", &r1, &c1, &r2, &c2);

    // Read second invigilator's region  
    int r3, c3, r4, c4;
    scanf("%d %d %d %d", &r3, &c3, &r4, &c4);

    // Check if Mahek is in first invigilator's region
    int in_first = (mahek_row >= r1 && mahek_row <= r2 && 
                    mahek_col >= c1 && mahek_col <= c2);

    // Check if Mahek is in second invigilator's region
    int in_second = (mahek_row >= r3 && mahek_row <= r4 && 
                     mahek_col >= c3 && mahek_col <= c4);

    // If Mahek is NOT in either region, he can cheat safely
    if (!in_first && !in_second) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }

    return 0;
}

Math, Hashing, Implementation, Prefix sum, Sliding Window

This problem can be done using the prefix sum kind of logic. In C++, it provides a functionality of a map, which stores in a key-value fashion. We start iterating from the 0^th index taking sum of the array, for every index, we store the index of latest possible sum % k to find the minimum length of r — l + 1. Then, from the formula for prefix sum on subarrays, if (prefix[r]-prefix[l-1]) % k = 0, then prefix[r] % k = prefix[l-1] % k, and the entry for map[0] will be initialized with -1 to preserve the structure of the problem. Then, for every index, we check whether sum % k belong in the map or not, if it does belong, then we take the min length of every possible subarray and store it in the variable, which will give us the final answer.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;  // Number of test cases
    
    while (t--) {
        int n;
        long long k;
        cin >> n >> k;
        
        vector a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];  // Input array elements
        }
        
        // Map to store the last seen index for each prefix sum remainder modulo k
        map<long long, int> seen;
        seen[0] = -1;  // Initialize remainder 0 at index -1
        
        long long prefix = 0;
        int ans = n + 1;  // Initialize with a value larger than maximum possible
        
        for (int i = 0; i < n; i++) {
            prefix = (prefix + a[i]) % k;
            
            // Normalize remainder to be in range [0, k-1]
            long long rem = prefix;
            if (rem < 0) rem += k;
            
            // Check if we've seen this remainder before
            if (seen.find(rem) != seen.end()) {
                int prev = seen[rem];
                ans = min(ans, i - prev);  // Update minimum subarray length
            }
            
            // Update the last seen index for this remainder
            seen[rem] = i;
        }
        
        // Output result
        if (ans == n + 1) {
            cout << -1 << "\n";  // No valid subarray found
        } else {
            cout << ans << "\n";  // Minimum length of subarray divisible by k
        }
    }
    
    return 0;
}