Problem Statement
Bob is a maths teacher of a class of N students. The examination results are out, and the marks obtained by the students are stored in the array marks. Bob is happy with the performance and decides to gift every student in his class an equal number of balls.
As Bob loves mathematics, he decides to pick a number that is a factor of the marks of all N students in his class and decides to gift that number of balls to every student.
However, Bob can change the marks of at most one student to any positive number of his choice so that he can distribute the maximum number of balls to the students.
Task Determine the maximum number of balls Bob can give to every student after changing the marks of at most one student to any positive number of his choice.
Example
Assumptions:
N = 3Marks = [12, 3, 11]Approach:The maximum possible number of balls each student can have is 3.Here, Bob can change the marks of the 3rd student to 39, allowing every student to receive 3 balls.
Sample Output:
The output is 3.
Function DescriptionComplete the max_balls function provided in the editor. This function takes the following two parameters and returns an integer that represents the answer to the task:
N: The number of students in the class.marks: An array representing the marks of N students.Input Format
N.N space-separated integers denoting the values in the array marks.Output Format Print an integer representing the maximum number of balls Bob can give to every student.
Constraints
2 ≤ N ≤ 10^51 ≤ marks[i] ≤ 10^9#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++) cin>>arr[i];
int ans=INT_MAX;
for(int i=1;i<n;i++){
int x=gcd(arr[i],arr[i-1]);
if(x!=1) ans=min(ans,x);
}
if(ans==INT_MAX) {
cout<<1<<"\n";
}
else {
cout<<ans<<"\n";
}
return 0;
}
Problem Statement
You are given a connected undirected graph having N nodes and M edges between the nodes. It is guaranteed that the input graph is connected and consists of no self-loops and no multiple edges between two vertices.
An edge is considered special if, when removed, the number of connected components in the graph increases.
Task
Determine the number of unordered pairs of nodes (u, v) such that every simple path (path with no repeated edges) between node u and node v consists of exactly 1 special edge.
Example
Assumptions:
N = 4, M = 4Edges = [(1, 2), (2, 3), (3, 4), (2, 4)]Approach:
In this graph, the paths between nodes (1, 2), (1, 3), and (1, 4) consist of exactly one special edge, which is the edge [1, 2].
Hence, the answer is 3.
Function DescriptionComplete the function special_sol provided in the editor. This function takes the following parameters and returns the required answer:
N: The number of nodes in the graph.M: The number of edges in the graph.Edg: A list of edges between two nodes in the graph.Input Format
T, denoting the number of test cases.N, representing the number of nodes in the graph.M, representing the number of edges in the graph.M lines contain integers ui and vi, denoting an edge between vertex ui and vertex vi.Output Format
For each test case, print an integer in a new line, denoting the number of unordered pairs (u, v) such that there is exactly 1 special edge in every simple path between them.
Constraints
1 ≤ T ≤ 101 ≤ N, M ≤ 2 x 10^51 ≤ u_i, v_i ≤ Nu_i ≠ v_i#include <bits/stdc++.h>
using namespace std;
class DSU
{
public:
vector<int> parent, rank, size;
DSU(int n)
{
parent.resize(n);
rank.resize(n);
size.resize(n);
// try{
// iota(parent.begin(), parent.end(), 0);
// }catch(exception e){
// cout<<e.what();
// }
iota(parent.begin(), parent.end(), 0);
fill(size.begin(), size.end(), 1);
fill(rank.begin(), rank.end(), 0);
}
int findParent(int node)
{
if (parent[node] == node)
{
return node;
}
return parent[node] = findParent(parent[node]);
}
void unionByRank(int u, int v)
{
int pu = findParent(u);
int pv = findParent(v);
if (pu == pv)
return;
if (rank[pu] < rank[pv])
{
parent[pu] = pv;
}
else if (rank[pu] > rank[pv])
{
parent[pv] = pu;
}
else
{
parent[pu] = pv;
rank[pv]++;
}
}
void unionBySize(int u, int v)
{
int pu = findParent(u);
int pv = findParent(v);
if (pu == pv)
return;
if (size[pu] < size[pv])
{
parent[pu] = pv;
size[pv] += size[pu];
}
else
{
parent[pv] = pu;
size[pu] += size[pv];
}
}
};
int timer = 1;
void dfs(int node, int parent, vector<int> adj[], int low[], int tin[], vector<int> &vis, vector<vector<int>> &bridges)
{
vis[node] = 1;
tin[node] = low[node] = timer;
timer++;
for (auto it : adj[node])
{
if (it == parent)
continue;
if (vis[it] == 0)
{
dfs(it, node, adj, low, tin, vis, bridges);
// done the dfs and came back to node or parent
low[node] = min(low[node], low[it]);
// if the low of the child is greater than the tin of the parent then it is a bridge
if (low[it] > tin[node])
{
bridges.push_back({node, it});
}
}
else
{
low[node] = min(low[node], tin[it]);
}
}
}
int main()
{
int n, m;
cin >> n >> m;
vector<int> adj[n];
while (m--)
{
int x, y;
cin >> x >> y;
// cout<<x<<" "<<y<<"\n";
adj[x - 1].push_back(y - 1);
adj[y - 1].push_back(x - 1);
}
int low[n];
int tin[n];
vector<int> vis(n, 0);
vector<vector<int>> bridges;
dfs(1, -1, adj, low, tin, vis, bridges);
// for (int i = 0; i < bridges.size(); i++)
// {
// cout << bridges[i][0] << " " << bridges[i][1] << "\n";
// }
DSU dsu(n);
set<pair<int, int>> st;
for (int i = 0; i < bridges.size(); i++)
{
st.insert({bridges[i][0], bridges[i][1]});
}
for (int i = 0; i < n; i++)
{
for (auto it : adj[i])
{
if (st.find({i, it}) == st.end() && st.find({it, i}) == st.end())
{
dsu.unionBySize(i, it);
}
}
}
long long int ans = 0;
for (auto it : st)
{
int u = it.first;
int v = it.second;
int x = dsu.size[dsu.findParent(u)];
int y = dsu.size[dsu.findParent(v)];
ans += x * 1LL * y;
}
cout << ans << "\n";
return 0;
}
Given an undirected graph consisting of (N) nodes. Each node has a number written on it, represented in an array arr of (N) distinct integers. There is an edge between two nodes (i) and (j) if:
LCM (a[i],a[j]) <= 10^6
Where the LCM of two numbers is the smallest positive integer that is divisible by both of them.
Print the number of connected components in this graph.
Complete the function solve which takes the following 2 parameters and returns the number of connected components:
N: Integer representing the size of array arr.arr: Array of (N) distinct integers representing the numbers written on the nodes.arr.Input:
3
2 1000000 999999
Output:
2
Constraints
1 <= N <= 10^6
1 <= arr[i] <= 10^9
Explanation: For (i = 1) and (j = 2), (\text{LCM}(2, 1000000) \leq 10^6). Therefore, there is an edge between 1 and 2.
For (i = 2) and (j = 3), (\text{LCM}(1000000, 999999) > 10^6). No edge exists between 2 and 3.
For (i = 1) and (j = 3), (\text{LCM}(2, 999999) > 10^6). No edge exists between 1 and 3.
The components are ([1, 2]) and ([3]). Hence, the answer is 2.
// Time Complexity: O(n^2) : Worst Solution
#include <bits/stdc++.h>
#define int long long
#define PI 3.141592653589793238462
#define set_bits __builtin_popcount
const int mod = (1e9 + 7);
const int N = (1e5 + 5);
using namespace std;
void dfs(int node, vector<int> adj[], vector<int> &vis)
{
vis[node] = 1;
for (auto it : adj[node])
{
if (vis[it] == 0)
{
dfs(it, adj, vis);
}
}
}
signed main()
{
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
vector<int> adj[n];
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
int hcf = gcd(arr[i], arr[j]);
int lcm = (arr[i] / hcf) * arr[j];
if (lcm <= 1e6)
{
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
int cnt = 0;
vector<int> vis(n, 0);
for (int i = 0; i < n; i++)
{
if (!vis[i])
{
cnt++;
dfs(i, adj, vis);
}
}
cout << cnt << endl;
return 0;
}
// Time Complexity: O(n * sqrt(m) + n * log n)
#include <bits/stdc++.h>
#define int long long
#define PI 3.141592653589793238462
#define set_bits __builtin_popcount
const int mod = (1e9 + 7);
const int N = (1e5 + 5);
using namespace std;
class DSU
{
public:
vector<int> parent, rank, size;
DSU(int n)
{
parent.resize(n + 1);
rank.resize(n + 1);
size.resize(n + 1);
iota(begin(parent), end(parent), 0);
fill(begin(size), end(size), 1);
fill(begin(rank), end(rank), 0);
}
int findParent(int node)
{
if (parent[node] == node)
return node;
return parent[node] = findParent(parent[node]);
}
void unionByRank(int u, int v)
{
int pu = findParent(u);
int pv = findParent(v);
if (pu == pv)
return;
if (rank[pu] < rank[pv])
parent[pu] = pv;
else if (rank[pv] < rank[pu])
parent[pv] = pu;
else
{
rank[pu]++;
parent[pv] = pu;
}
}
void rankBySize(int u, int v)
{
int pu = findParent(u);
int pv = findParent(v);
if (pu == pv)
return;
if (size[pu] < size[pv])
{
parent[pu] = pv;
size[pv] += size[pu];
}
else if (size[pv] < size[pu])
{
parent[pv] = pu;
size[pu] += size[pv];
}
else
{
parent[pu] = pv;
size[pv] += size[pu];
}
}
};
void dfs(int node, vector<int> adj[], vector<int> &vis)
{
vis[node] = 1;
for (auto it : adj[node])
{
if (vis[it] == 0)
{
dfs(it, adj, vis);
}
}
}
vector<int> primeFactors(int n)
{
vector<int> factors;
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
factors.push_back(i);
while (n % i == 0)
{
n /= i;
}
}
}
if (n > 1)
{
factors.push_back(n);
}
return factors;
}
signed main()
{
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
DSU dsu(n);
unordered_map<int, int> prime_map;
for (int i = 0; i < n; i++)
{
vector<int> factors = primeFactors(arr[i]);
for (auto prime : factors)
{
if (prime_map.find(prime) != prime_map.end())
{
dsu.unionByRank(i, prime_map[prime]);
}
else
{
prime_map[prime] = i;
}
}
}
unordered_set<int> unique_components;
for (int i = 0; i < n; i++)
{
unique_components.insert(dsu.findParent(i));
}
cout << unique_components.size() << endl;
return 0;
}
Given (N) coins with values ranging from 0 to (N-1), your friend wants to take (K) coins out of your collection. You can only give them a set of coins if the sum of the chosen coins is divisible by a given integer (M).
Find the number of ways in which your friend can get (K) coins such that the sum of the coins is divisible by (M).
Since the answer can be large, return the answer modulo (10^5 + 7).
Complete the function solve which takes the following 3 parameters and returns the number of ways:
N: Integer representing the number of coins.K: Integer representing the number of coins your friend wants.M: Integer representing the divisor for the sum of the chosen coins.Input:
4 2 2
Output:
2
Explanation: There are two ways to choose the coins:
Hence, the answer is 2.
#include <bits/stdc++.h>
using namespace std;
int recursion(int ind, int k, int m, int sum, vector<int> &coins)
{
if (k == 0)
{
if (sum % m == 0)
return 1;
return 0;
}
if (ind < 0)
return 0;
int notTake = recursion(ind - 1, k, m, sum, coins);
int take = recursion(ind - 1, k - 1, m, (sum + coins[ind]) % m, coins);
return take + notTake;
}
int main()
{
int n, k, m;
cin >> n >> k >> m;
vector<int> coins(n);
iota(begin(coins), end(coins), 0);
cout<<recursion(n - 1, k, m, 0, coins);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int recursion(int ind, int k, int m, int sum, vector<int> &coins, vector<vector<vector<int>>> &dp)
{
if (k == 0)
{
if (sum % m == 0)
return 1;
return 0;
}
if (ind < 0)
return 0;
if (dp[ind][k][sum] != -1)
return dp[ind][k][sum];
int notTake = recursion(ind - 1, k, m, sum, coins, dp) % mod;
int take = recursion(ind - 1, k - 1, m, (sum + coins[ind]) % m, coins, dp) % mod;
return dp[ind][k][sum] = (take + notTake) % mod;
}
int main()
{
int n, k, m;
cin >> n >> k >> m;
vector<int> coins(n);
iota(begin(coins), end(coins), 0);
vector<vector<vector<int>>> dp(n, vector<vector<int>>(k + 1, vector<int>(m + 1, -1)));
cout << recursion(n - 1, k, m, 0, coins, dp) << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int main()
{
int n, k, m;
cin >> n >> k >> m;
vector<vector<int>> dp(k + 1, vector<int>(m + 1));
dp[0][0] = 1;
for (int i = 0; i < n; i++)
{
for (int j = k - 1; j >= 0; j--)
{
for (int rem = 0; rem < m; rem++)
{
int nm = (i + rem) % m;
dp[j + 1][nm] = (dp[j + 1][nm] + dp[j][rem]) % mod;
}
}
}
cout << dp[k][0] << endl;
return 0;
}
#include <bits/stdc++.h>
#define int long long
#define PI 3.141592653589793238462
#define set_bits __builtin_popcount
const int mod = (1e9 + 7);
const int N = (1e5 + 5);
using namespace std;
void solve()
{
}
signed main()
{
int i, n;
char *x = "Hacker";
n = strlen(x);
*x=x[n];
for (i = 0; i <= n; i++)
{
printf("%s", x);
}
printf("\n",x);
return 0;
}
In C++, static polymorphism is achieved through function overloading and template programming. One common example is function overloading, where multiple functions share the same name but have different parameter lists, allowing the compiler to choose the correct function at compile time.
Here’s a simple example using function overloading:
#include <iostream>
using namespace std;
class Math {
public:
// Overloaded function for adding integers
int add(int a, int b) {
return a + b;
}
// Overloaded function for adding doubles
double add(double a, double b) {
return a + b;
}
// Overloaded function for adding three integers
int add(int a, int b, int c) {
return a + b + c;
}
};
int main() {
Math mathObj;
// Calls add(int, int)
cout << "Sum of 2 and 3: " << mathObj.add(2, 3) << endl;
// Calls add(double, double)
cout << "Sum of 2.5 and 3.7: " << mathObj.add(2.5, 3.7) << endl;
// Calls add(int, int, int)
cout << "Sum of 1, 2, and 3: " << mathObj.add(1, 2, 3) << endl;
return 0;
}
Output:
Sum of 2 and 3: 5
Sum of 2.5 and 3.7: 6.2
Sum of 1, 2, and 3: 6
In this example:
The add function is overloaded to handle different numbers of arguments and different types (integers and doubles).
The compiler selects the appropriate function based on the argument types at compile time, demonstrating static polymorphism.
Yes, operator overloading in C++ can be considered an example of static polymorphism because the decision of which overloaded operator function to invoke is made at compile time.
In operator overloading, just like function overloading, multiple versions of the same operator (like +, -, etc.) can be defined for different types or scenarios. The compiler determines which operator to invoke based on the operands' types at compile time, which makes it a form of static (compile-time) polymorphism.
Example:
#include `<iostream>`
using namespace std;
class Complex {
private:
double real, imag;
public:
// Constructor
Complex(double r, double i) : real(r), imag(i) {}
// Overloading the + operator
Complex operator + (const Complex& obj) {
return Complex(real + obj.real, imag + obj.imag);
}
void display() {
cout << real << " + " << imag << "i" << endl;
}
};
int main() {
Complex c1(2.5, 3.5);
Complex c2(1.5, 2.0);
Complex c3 = c1 + c2; // Calls overloaded + operator
cout << "Result of c1 + c2: ";
c3.display();
return 0;
}
Output:
Result of c1 + c2: 4 + 5.5i
Here:
The + operator is overloaded to add two Complex numbers.
The decision about which + operator to use is resolved at compile time, hence it qualifies as static polymorphism.
Summary:
Yes, operator overloading is a form of static polymorphism because the overloaded operators are resolved during compile time, similar to function overloading.
Which of the following statements is correct about RDBMS?
Statement 1: RDBMS contains normalization.
Statement 2: Distributed data databases are not supported by RDBMS.
Options:
1. Only 1
2. Only 2
3. Both 1 and 2
4. None of these
The correct answer is "only 1".
Explanation:
This statement is correct. Normalization is a process used in relational databases to organize data to reduce redundancy and improve data integrity. RDBMSs support and encourage normalization to ensure efficient and accurate data storage.
This statement is incorrect. Modern RDBMSs do support distributed databases. Many RDBMSs, like MySQL, PostgreSQL, and Oracle, provide mechanisms for distributed database architectures where data can be spread across multiple locations or systems while still maintaining consistency and integrity.
Conclusion:
Thus, the correct option is "only 1" because the first statement is true and the second one is false.
Function Overloading: Defining multiple functions with the same name but different parameters.
Operator Overloading: Defining custom behavior for operators like +, -, etc., for user-defined types.
Template Polymorphism: Using templates to write generic functions or classes that work with any data type.
Inheritance and Virtual Functions: When a derived class overrides a base class method, the method to be invoked is determined at runtime based on the type of the object pointed to or referenced.
Compile-time (Static) polymorphism:
Function Overloading
Operator Overloading
Template Polymorphism
Run-time (Dynamic) polymorphism:
Virtual Functions (through inheritance)
In Data Structures, what is the best-case and worst-case time complexity analysis for the following pseudocode in the insertion sort algorithm?
final Node<E> sorted = null;
Node<E> current = first;
while (current != NULL) {
Node<E> next = current.next;
Unlink(current);
sortedInsert(current.data);
current = next;
}
Options:
1. Best-case: O(n), Worst-case: O(n^2)
2. Best-case: O(n^2), Worst-case: O(n)
3. Best-case: O(log n), Worst-case: O(n log n)
4. None of these
To analyze the time complexity of the given pseudocode, which appears to implement the insertion sort algorithm, we need to understand the key operations within it.
The pseudocode iterates over a linked list of nodes (Node
Insertion Sort Time Complexity Analysis:
The best case occurs when the input list is already sorted. In this scenario, each new element is simply compared once with the last element of the sorted list.
In the best case, each insertion takes constant time (O(1)), and since there are n elements, the best-case time complexity is O(n).
The worst case occurs when the input list is sorted in reverse order. In this case, every new element has to be compared with every element already in the sorted list, resulting in comparisons that grow as the sorted list increases in size.
The worst-case time complexity of insertion sort is O(n^2) because for every element, it might need to be compared with all the previously sorted elements, leading to a quadratic number of comparisons.
Conclusion:
Best-case complexity: O(n) (when the list is already sorted)
Worst-case complexity: O(n^2) (when the list is in reverse order)