CodeQuest 2024 - Algozenith VIIT
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:
*
***
*****
*******
*********
2
3
5
*
***
*****
*
***
*****
*******
*********
Solution
Click to expand solution
#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, wherei
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
.
- 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
- 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
.
2. Cookie Distribution
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
2
1 2 3
1 1
1 2
1 2 3
1
2
Solution
Click to expand solution
#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
andj
) to traverse the sorted lists. Pointeri
traverses the greed factors, and pointerj
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
andj
) and increase the count of satisfied children. If not, just move to the next cookie by incrementing pointerj
. - 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 i
th 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]]
1
4
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
1
4
10 20
30 200
50 30
200 50
120
Solution
Click to expand solution
#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.
2
10
1 2 4 3 3 2 2 3 1 1
4
0 0 0 1
4
1
Solution
Click to expand solution
#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 ≤ 105
-
1 ≤ A[i] ≤ 109
Input Format
- The input consists of a single integer array
A
of sizeN
.
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 is1
.
Explanation 2:
- If you remove either
A[0]
(5) orA[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.
- For
- Thus, both
A[0]
andA[1]
are special elements, making the count2
.
1
4
2 1 6 4
1
Solution
Click to expand solution
#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:
1
\
2
/
3
Input 2:
1
/ \
6 2
/
3
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
1
1 2 3 4 5
1 2 4 5 3
Solution
Click to expand solution
#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 ≤ 105
1
1 2 3 4 5 6 7 N N N N N 8 N 9
4 2 1 5 6 3 8 7 9
Solution
Click to expand solution
#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.
1
abcabcbb
3
Solution
Click to expand solution
#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.