CodeQuest 2024 - Algozenith VIIT | by Gautam Ankoji | September 5, 2024 | Articles

1. Vercel Star Pattern

Problem Statement

Swathi mam, your Web Development teacher, is excited about the Teacher's Day celebrations and wants to teach her students how to create a star pattern that resembles the Vercel logo. To help her, you need to write a program that prints this pattern.

Given a positive integer n, representing the number of rows, your task is to print a star pattern with n rows. The pattern should have a centered triangle shape where each row contains an increasing number of stars.

Example

Example 1:

Input: n = 5

Output:

    *
   ***
  *****
 *******
*********

Sample Input

2
3
5

Sample Ouput

  *
 ***
*****
    *
   ***
  *****
 *******
*********

Solution

Click to expand solution

solution.cpp

solution.py

Solution.java

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            for (int j = n; j > i + 1; j--)
                cout << " ";
            for (int j = 0; j <= i * 2; j++)
                cout << "*";
            cout << endl;
        }
    }
    return 0;
}

Explanation

Generating the Pattern:

The outer loop runs n times, where i represents the current row.
For each row:
- Spaces: The first inner loop prints spaces. The number of spaces decreases as the row number increases. This ensures that the stars are centered. The number of spaces is n - i - 1.
- Stars: The second inner loop prints stars. The number of stars increases with each row, and it is calculated as 2 * i + 1.
After printing the stars for the current row, a newline is printed to move to the next row.

The solution is efficient with a time complexity of O(n^2) due to the nested loops and works well for reasonably sized values of n.

Problem Statement

It's Teacher's Day, and Swathi mam wants to make her students happy by giving them cookies. But there's a catch—each student can receive only one cookie. Every student has a greed factor, which represents the minimum size of the cookie that will make them happy. Each cookie has a size. If the size of a cookie is greater than or equal to the greed factor, Swathi mam can give that cookie to the student, making them content. Your task is to help Swathi mam distribute the cookies in a way that maximizes the number of happy students.

Determine and output the maximum number of students that can be content with the cookies they receive.

Examples

Example 1:

Input: g = [1, 2, 3], s = [1, 1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content. You need to output 1.

Example 2:

Input: g = [1, 2], s = [1, 2, 3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. You have 3 cookies and their sizes are big enough to gratify all of the children. You need to output 2.

Constraints

1 <= g.length <= 30,000
0 <= s.length <= 30,000
1 <= g[i], s[j] <= 2^31 - 1

Sample Input

Sample Ouput

1
2

Solution

Click to expand solution

solution.cpp

solution.py

Solution.java

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findContentChildren(vector<int> &g, vector<int> &s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int i = 0, j = 0, count = 0;
    while (i < g.size() && j < s.size()) {
        if (s[j] >= g[i]) {
            count++;
            i++;
            j++;
        } else {
            j++;
        }
    }
    return count;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;        
        cin >> n;
        vector<int> g(n);
        for (int i = 0; i < n; i++) {
            cin >> g[i];
        }        
        cin >> m;
        vector<int> s(m);
        for (int i = 0; i < m; i++) {
            cin >> s[i];
        }        
        cout << findContentChildren(g, s) << endl;
    }
    return 0;
}

Explanation

Approach:

Sorting: First, sort both the greed factors list (g) and the cookie sizes list (s). This allows for a straightforward comparison from the smallest to the largest.
Two-pointer Technique: Use two pointers (i and j) to traverse the sorted lists. Pointer i traverses the greed factors, and pointer j traverses the cookie sizes.
Matching Cookies: For each cookie size, check if it can satisfy the current greed factor. If yes, increment both pointers (i and j) and increase the count of satisfied children. If not, just move to the next cookie by incrementing pointer j.
Termination: The process stops when either all children have been considered or all cookies have been used.

The solution efficiently finds the maximum number of content children by ensuring each child gets the smallest possible cookie that satisfies their greed factor.

3. Interview Flight Cost

Problem Statement

To celebrate Teacher's Day, Prasad Sir, the Training and Placement faculty, is organizing interviews for a company that plans to interview 2n candidates. Given the array costs where costs[i] = [aCost[i], bCost[i]], each candidate has a choice between two cities, A and B. The cost to fly the ith candidate to city A is aCost[i], and to city B is bCost[i]. Your task is to determine the minimum cost to fly every candidate such that exactly n candidates arrive in each city.

Example

Input: costs = [[10, 20], [30, 200], [50, 30], [200, 50]]

Output: 120

Explanation:

Send the first and third candidates to city A.
Send the second and fourth candidates to city B.
The total cost will be 10 + 50 + 200 + 50 = 310.

Constraints

2 * n == costs.length
2 <= costs.length <= 100
costs.length is even.
1 <= aCost[i], bCost[i] <= 1000

Sample Input

Sample Ouput

Solution

Click to expand solution

solution.cpp

solution.py

Solution.java

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int twoCitySchedCost(vector<vector<int>>& costs) {
    for (int i = 0; i < costs.size(); i++) {
        costs[i].push_back(costs[i][0] - costs[i][1]);
    }
    sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[2] < b[2];
    });
    int s = 0;
    int n = costs.size() / 2;
    for (int i = 0; i < n; i++) {
        s += costs[i][0];
    }
    for (int i = n; i < 2 * n; i++) {
        s += costs[i][1];
    }
    return s;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<vector<int>> costs(n, vector<int>(2));
        for (int i = 0; i < n; i++) {
            cin >> costs[i][0] >> costs[i][1];
        }
        cout << twoCitySchedCost(costs) << endl;
    }
    return 0;
}

Explanation

Approach:

Compute Differences: For each candidate, compute the difference between the cost of flying to city A and city B and append this difference to the list of costs.
Sort by Difference: Sort the candidates based on this difference. This sorting helps in deciding which candidates are more 'cost-effective' to send to which city.
Select Candidates: From the sorted list, select the first half of the candidates to fly to city A and the remaining half to city B. This ensures that the cost is minimized while balancing the number of candidates in each city.
Compute Total Cost: Sum the costs based on the selected cities for each candidate.

The solution is efficient with a time complexity of O(n log n) due to sorting and handles the constraints effectively.

4. Unique Element Challenge

Problem Statement

To celebrate Teacher's Day, Santosh Sir, the Training and Placement faculty, has a special challenge for his students. He gives them an array of integers where every element appears three times except for one unique element that appears only once. Your task is to find that unique element which does not appear thrice. To make it more exciting, Prasad Sir asks if you can solve this challenge with linear runtime complexity and without using extra memory.

Input Format

The first and only argument of input contains an integer array A.

Output Format

Return a single integer which is the unique element that does not appear thrice.

Example

Input 1: A = [1, 2, 4, 3, 3, 2, 2, 3, 1, 1]

2
10
1 2 4 3 3 2 2 3 1 1

Output 1: 4

Input 2: A = [0, 0, 0, 1]

4
0 0 0 1

Output 2: 1

Explanation:

In Input 1, the number 4 occurs exactly once while all other numbers occur thrice.
In Input 2, the number 1 occurs exactly once while 0 occurs thrice.

Constraints

The array length can be quite large, but your solution should handle it efficiently.

Sample Input

2
10
1 2 4 3 3 2 2 3 1 1
4
0 0 0 1

Sample Ouput

4
1

Solution

Click to expand solution

solution.cpp

solution.py

Solution.java

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

int singleNumber(const vector<int> &A) {
    vector<int> v(32, 0);
    for (int i : A) {
        for (int j = 0; j < 32; j++)
            if (i >> j & 1)
                v[j]++;
    }
    int ans = 0;
    for (int i = 0; i < 32; i++)
        if (v[i] % 3)
            ans += (1 << i);
    return ans;
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cout << (singleNumber(a)) << endl;
    }
}

Explanation

Approach:

Bit Manipulation: We use a bit manipulation technique to find the unique number. We maintain a 32-bit array v to count the number of times each bit is set across all numbers in the input array.
Modulo Operation: After counting, for each bit position j, if the count is not divisible by 3, then it means the unique number has that bit set.
Reconstruction of the Unique Number: Finally, we reconstruct the unique number by checking which bit positions have counts that are not divisible by 3, and summing their respective powers of two.

This approach ensures that the solution works in linear time O(n) and does not require extra space except for the bit counting array, making it highly efficient.

5. Special Elements in a Balanced Array

Problem Statement

In honor of Dinesh Sir, our esteemed CSE HOD, we present a problem inspired by his style. Known for his challenging and elegant coding problems, this task reflects his dedication to balancing complexity with simplicity. We hope this problem inspires you as much as his contests inspire us!

Problem Description

Dinesh Sir always emphasizes the importance of balance in programming and problem-solving. Today, you are given a task that mirrors this principle.

You have been provided with an integer array A of size N. Your goal is to determine the number of special elements in the array.

An element in the array is considered special if, upon its removal, the remaining array becomes balanced. An array is considered balanced if the sum of the elements at even indices is equal to the sum of the elements at odd indices.

Problem Constraints

1 ≤ N ≤ 10⁵
1 ≤ A[i] ≤ 10⁹

Input Format

The input consists of a single integer array A of size N.

Output Format

Return an integer representing the count of special elements in the array.

Example Input

Input 1: A = [2, 1, 6, 4]

Input 2: A = [5, 5, 2, 5, 8]

Example Output

Output 1: 1

Output 2: 2

Example Explanation

Explanation 1:

If you remove the element 1 from the array, you are left with [2, 6, 4]. The sum of the elements at even indices (2 + 4) equals the sum of the element at the odd index (6). Thus, 1 is the only special element, so the count is 1.

Explanation 2:

If you remove either A[0] (5) or A[1] (5), the remaining array will be balanced. In both cases:
- For A[0]: The remaining array is [5, 2, 5, 8], with even indices sum (5 + 5) and odd indices sum (2 + 8) being equal.
- For A[1]: The remaining array is [5, 2, 5, 8], with even indices sum (5 + 5) and odd indices sum (2 + 8) being equal.
Thus, both A[0] and A[1] are special elements, making the count 2.

Sample Input

1
4
2 1 6 4

Sample Ouput

Solution

Click to expand solution

solution.cpp

solution.py

Solution.java

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

int solve(vector<int> &A) {
    int n = A.size();
    int odd = 0, even = 0;
    int leftOdd[n], rightOdd[n];
    int leftEven[n], rightEven[n];
    for (int i = 0; i < n; i++) {
        leftOdd[i] = odd;
        leftEven[i] = even;
        if (i % 2 == 0)
            even += A[i];
        else
            odd += A[i];
    }
    odd = 0;
    even = 0;
    for (int i = n - 1; i >= 0; i--) {
        rightOdd[i] = odd;
        rightEven[i] = even;
        if (i % 2 == 0)
            even += A[i];
        else
            odd += A[i];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (leftOdd[i] + rightEven[i] == leftEven[i] + rightOdd[i]) {
            ans++;
        }
    }
    return ans;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cout << solve(a) << endl;
    }
}

Explanation of Approach

The approach leverages prefix and suffix sums to calculate the sums of even and odd indices from both directions. For each element in the array, we check if its removal results in the sums of even and odd indexed elements being equal. The overall time complexity is (O(N)), ensuring it handles large inputs efficiently.

6. Usha Mam's Postorder Puzzle

Problem Statement

In honor of Usha Rani Mam, our esteemed DAA faculty known for her insightful problem-solving techniques, we present a challenge in her style. Your task is to perform a Postorder traversal of a binary tree.

In Postorder traversal, you first visit the left subtree, then the right subtree, and finally the root node. This time, you are required to solve the problem without using recursion.

Input Format

You are given the root node of a binary tree.

Output Format

Return an integer array representing the Postorder traversal of the binary tree.

Example Input

Input 1:

Input 2:

Example Output

Output 1: [3, 2, 1]

Output 2: [6, 3, 2, 1]

Example Explanation

Explanation 1: The Postorder traversal of the given tree is [3, 2, 1]. You visit the left subtree (3), then the right subtree (2), and finally the root node (1).

Explanation 2: The Postorder traversal of the given tree is [6, 3, 2, 1]. You visit the left subtree (6), then the right subtree (3, 2), and finally the root node (1).

Constraints

1 ≤ ext{number of nodes} ≤ 10^5

Sample Input

1
1 2 3 4 5

Sample Ouput

1 2 4 5 3

Solution

Click to expand solution

solution.cpp

solution.py

Solution.java

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

struct Node {
    int data;
    Node *left;
    Node *right;
};

Node *newNode(int val) {
    Node *temp = new Node;
    temp->data = val;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

Node *buildTree(string str) {
    if (str.length() == 0 || str[0] == 'N')
        return NULL;

    vector<string> ip;
    istringstream iss(str);
    for (string str; iss >> str;)
        ip.push_back(str);

    Node *root = newNode(stoi(ip[0]));
    queue<Node *> queue;
    queue.push(root);

    int i = 1;
    while (!queue.empty() && i < ip.size()) {
        Node *currNode = queue.front();
        queue.pop();

        string currVal = ip[i];
        if (currVal != "N") {
            currNode->left = newNode(stoi(currVal));
            queue.push(currNode->left);
        }
        i++;
        if (i >= ip.size())
            break;

        currVal = ip[i];
        if (currVal != "N") {
            currNode->right = newNode(stoi(currVal));
            queue.push(currNode->right);
        }
        i++;
    }

    return root;
}

vector<int> postOrderTraversal(Node *root) {
    vector<int> result;
    if (root == NULL)
        return result;

    stack<Node *> s1, s2;
    s1.push(root);

    while (!s1.empty()) {
        Node *node = s1.top();
        s1.pop();
        s2.push(node);

        if (node->left)
            s1.push(node->left);
        if (node->right)
            s1.push(node->right);
    }

    while (!s2.empty()) {
        result.push_back(s2.top()->data);
        s2.pop();
    }

    return result;
}

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

    while (t--) {
        string s;
        getline(cin, s);

        Node *root = buildTree(s);
        vector<int> result = postOrderTraversal(root);

        for (int i = 0; i < result.size(); i++)
            cout << result[i] << " ";
        cout << endl;
    }

    return 0;
}

Explanation of Approach

The problem can be solved by using two stacks to simulate Postorder traversal without recursion. The first stack is used to traverse the tree in a manner similar to reverse Preorder (Root -> Right -> Left). The second stack then reverses this order to give the correct Postorder traversal (Left -> Right -> Root). The time complexity is (O(N)), ensuring that it can handle large inputs efficiently.

7. Vertical Order Traversal

Problem Statement

In the spirit of Teacher's Day, let's celebrate the guiding principles of structure and order that our teachers instill in us, much like the structure of a Binary Tree. Given a Binary Tree, your task is to return its Vertical Order Traversal, starting from the leftmost level to the rightmost level. If multiple nodes pass through a vertical line, print them as they appear in the level order traversal of the tree.

Examples

Example 1:

Input:

           1
         /   \
       2       3
     /   \   /   \
   4      5 6      7
              \      \
               8      9

Output: 4 2 1 5 6 3 8 7 9

Explanation:
The vertical order traversal proceeds level by level, left to right. The nodes are processed as follows: 4, 2, 1, 5, 6, 3, 8, 7, and 9.

Example 2:

Input:

       1
    /    \
   2       3
 /    \      \
4      5      6

Output: 4 2 1 5 3 6

Input Format

The root node of a Binary Tree.

Output Format

Return an integer array representing the Vertical Order Traversal of the tree.

Constraints

1 ≤ number of nodes ≤ 10⁵

Sample Input

1
1 2 3 4 5 6 7 N N N N N 8 N 9

Sample Ouput

4 2 1 5 6 3 8 7 9

Solution

Click to expand solution

solution.cpp

solution.py

Solution.java

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

struct Node {
    int data;
    Node *left;
    Node *right;
};

Node *newNode(int val) {
    Node *temp = new Node;
    temp->data = val;
    temp->left = NULL;
    temp->right = NULL;

    return temp;
}

Node *buildTree(string str) {
    if (str.length() == 0 || str[0] == 'N')
        return NULL;
    vector<string> ip;

    istringstream iss(str);
    for (string str; iss >> str;)
        ip.push_back(str);
    Node *root = newNode(stoi(ip[0]));
    queue<Node *> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < ip.size()) {
        Node *currNode = queue.front();
        queue.pop();
        string currVal = ip[i];
        if (currVal != "N") {
            currNode->left = newNode(stoi(currVal));
            queue.push(currNode->left);
        }
        i++;
        if (i >= ip.size())
            break;
        currVal = ip[i];
        if (currVal != "N") {
            currNode->right = newNode(stoi(currVal));
            queue.push(currNode->right);
        }
        i++;
    }

    return root;
}

void printInorder(Node *root) {
    if (!root)
        return;

    printInorder(root->left);
    cout << root->data << " ";
    printInorder(root->right);
}

class Solution {
  public:
    void find(Node *root, int pos, int &l, int &r) {
        if (!root)
            return;
        l = min(l, pos);
        r = max(r, pos);
        find(root->left, pos - 1, l, r);
        find(root->right, pos + 1, l, r);
    }
    vector<int> verticalOrder(Node *root) {
        vector<int> ans;

        int l = 0, r = 0;
        find(root, 0, l, r);
        vector<vector<int>> positive(r + 1);
        vector<vector<int>> negative(abs(l) + 1);
        queue<Node *> q;
        queue<int> index;
        q.push(root);
        index.push(0);
        while (!q.empty()) {
            Node *temp = q.front();
            q.pop();
            int pos = index.front();
            index.pop();
            if (pos >= 0)
                positive[pos].push_back(temp->data);
            else
                negative[abs(pos)].push_back(temp->data);
            if (temp->left) {
                q.push(temp->left);
                index.push(pos - 1);
            }
            if (temp->right) {
                q.push(temp->right);
                index.push(pos + 1);
            }
        }

        for (int i = negative.size() - 1; i > 0; i--) {
            for (int j = 0; j < negative[i].size(); j++)
                ans.push_back(negative[i][j]);
        }
        for (int j = 0; j < positive.size(); j++) {
            for (int i = 0; i < positive[j].size(); i++)
                ans.push_back(positive[j][i]);
        }
        return ans;
    }
};

int main() {
    int t;
    string tc;
    getline(cin, tc);
    t = stoi(tc);
    while (t--) {
        string s;
        getline(cin, s);
        Solution obj;
        Node *root = buildTree(s);
        vector<int> res = obj.verticalOrder(root);
        for (int i : res)
            cout << i << " ";
        cout << endl;
    }
    return 0;
}

Explanation

This code efficiently solves the vertical order traversal of a binary tree using a breadth-first approach, keeping track of node positions relative to a vertical axis.

8. Longest Unique Substring Challenge

Problem Statement

In honor of Teacher's Day, we celebrate the uniqueness that each educator brings to their lessons. Given a string s, your task is to find the length of the longest substring that contains no repeating characters. Embrace this challenge and showcase your problem-solving skills!

Input Format

The first and only argument of input contains a string s.

Output Format

Return an integer representing the length of the longest substring without repeating characters.

Example

Input 1:
s = "abcabcbb"

Output 1:
3

Explanation:
The longest substring without repeating characters is "abc", which has a length of 3.

Input 2:
s = "bbbbb"

Output 2:
1

Explanation:
The longest substring without repeating characters is "b", which has a length of 1.

Input 3:
s = "pwwkew"

Output 3:
3

Explanation:
The longest substring without repeating characters is "wke", which has a length of 3. Note that "pwke" is a subsequence, not a substring.

Constraints

0 ≤ s.length ≤ 50,000
s consists of English letters, digits, symbols, and spaces.

Sample Input

1
abcabcbb

Sample Ouput

Solution

Click to expand solution

solution.cpp

solution.py

solution.java

#include <iostream>
#include <unordered_set>
#include <string>
#include <algorithm>
using namespace std;

int lengthOfLongestSubstring(const string& s) {
    unordered_set<char> chars;
    int best = 0;
    int l = 0;
    for (char i : s) {
        while (chars.find(i) != chars.end()) {
            chars.erase(s[l]);
            l++;
        }
        chars.insert(i);
        best = max(best, static_cast<int>(chars.size()));
    }
    return best;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        cout << lengthOfLongestSubstring(s) << endl;
    }
    return 0;
}

Explanation

Approach:

Sliding Window with Set: This problem can be efficiently solved using a sliding window approach. We maintain a window that stores unique characters and expand or shrink the window based on the condition of repeating characters.
Efficiency: By using a set to track the characters currently in the substring, and adjusting the left pointer when a duplicate is found, we ensure that the solution works in linear time O(n).
Final Answer: The length of the longest substring is updated dynamically as we traverse the string.

CodeQuest 2024 - Algozenith VIIT

1. Vercel Star Pattern

Problem Statement

Example

Solution

Explanation

2. Cookie Distribution

Problem Statement

Examples

Solution

Explanation

3. Interview Flight Cost

Problem Statement

Example

Solution

Explanation

4. Unique Element Challenge

Problem Statement

Input Format

Output Format

Example

Constraints

Solution

Explanation

5. Special Elements in a Balanced Array

Problem Statement

Problem Description

Problem Constraints

Input Format

Output Format

Example Input

Example Output

Example Explanation

Solution

Explanation of Approach

6. Usha Mam's Postorder Puzzle

Problem Statement

Input Format

Output Format

Example Input

Example Output

Example Explanation

Constraints

Solution

Explanation of Approach

7. Vertical Order Traversal

Problem Statement

Examples

Input Format

Output Format

Constraints

Solution

Explanation

8. Longest Unique Substring Challenge

Problem Statement

Input Format

Output Format

Example

Constraints

Solution

Explanation