Join Us
Loading Similar Posts
Entering edit mode
Question 1
Click here to Practice
Submit Problem to OJ
Divisor Friends
There are N students in a class, each student has their favorite number F, (given in form of an array F).
Student A is a friend of Student B if and only if any two conditions satisfies:
• There is a number × (x > 1) such that x divides favorite numbers of both A and B
• A is a friend of C and C is a friend of B.
Task Determine the minimum number of groups that can be formed where the students in each group are friends with each other. Each student must belong to at least one group.
Note: Assume 1-based indexing.
Example Assumptions
- N = 4
- F = [2,4,6,5]
Approach
- Here are four students 1, 2 , 3 , 4 and their favorite numbers are 2, 4, 6 and 5.
- 1, 2, and 3 are pairwise friends since x=2 divides the favorite number of all three of them.
- So, the minimum of two groups that can be formed are [1,2,3] and [4]
Function description
Complete the MimimumGroup() function provided in the editor. This function takes the following 2 parameters and returns the answer:
- N: Represents the number of students
- F. Represents the favorite numbers of N students
Input format
Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).
- The first line contains an integer N.
- The next line contains N space-separated integers denoting the favorite numbers of students.
Output format
Print a single integer representing the minimum number of groups that can be formed.
Constraints
1 < N < 105
2 <Fi < 106
Code snippets (also called starter code/boilerplate code)
This question has code snippets for C, CPP. Java, and Python.
Question 2
Click here to Practice
Submit Problem to OJ
Count Function
You are given the following:
• An integer N
• A string A consisting of lower case English alphabets and having length N
• An integer D
Consider a function which takes a character as an argument and returns the ASCII value of the character. For example, f(a) = 97.
Task
For each index i (1 <= i <= N), determine the count of all indices j, such that j> i and | f(Ai) - f(Aj) | <= D
Here Ix| denotes the absolute value of x. For example, |-3| = 3, |3| = 3.
Note: 1-based Indexing is followed.
Example
Assumptions
- T =1
- N =4
- A =”bbac”
- D =1
Approach
• You have f(a) = 97, f(b) = 98, f(c) = 99.
• For first character, you have i = 1, possible values of j > i such that | f(Ai) - f(Aj) | <= 1 are j = 2, 3, 4. Therefore, 3 such indices exist.
• For second character, you have i = 2, possible values of j > i such that | f(Ai) - f(Aj) | <= 1 are j = 3, 4.Therefore, 2 such indices exist.
• For third character, you have i = 3,there is no possible value of j>¡ such that | f(Ai) - f(Aj) | <= 1. Therefore, 0 such indices exist.
• For fourth character, you have i = 4,there is no possible value of j>i such that |f(Ai) - f(Aj)| <= 1.Therefore, 0 such indices exist.
• Therefore, the output is 3 2 0 0
Function Description
Complete the d_distance function provided in the editor. This function takes the following 3 parameters and returns an array/vector of integers of length N whose ith integer denotes the count of indices j>i such that | f(Ai) - f(Aj) | <= D:
• N: Represents the integer N
• A: Represents the string A
• D: Represent the integer D
Input format
Note: This is the input format that you must use to provide custom input.
Entering edit mode
Question 1(Divisor friends)
observations:
- If we know all the friends by rule 1 (
gcd(A,B)) greater than 1. - Take the students as vertices and friendship as edges
- Then we find by all the friends by rule 2 by checking there are connected are not
- Minimum number of groups needed is the number of Connected Components
Approach:
- Precompute all the prime factors of numbers from 1 to
10^6- A rough bound for the number of computation steps is
10^6*2010^6no of numbers- 20, because
2^20 > 10^6
- Exact count is
2853708.
- A rough bound for the number of computation steps is
- For all primes
i, store the indices of elements in the given array which are its multiples in multiples[i].- This would take
N*20at max - Stores indices of
A[j] =1inmultiples[1]
- This would take
- Now go to each prime number
i < 10^6and connect the adjacent elements in themultiples[i]array using a disjoint set union(DSU).- This would take care of both friendships of type 1 and type 2
- since every adjacent element is connected, all numbers which that prime factor are connected.
- since a student's favorite number's index is present in every of its prime factor's
multipleslist , the friendship of type 2 is also connected
- Now find the number of unique components, which equal to the number of elements for which
parent[i]=iin the dsu
Complexity
O(NLOGN+10^6log10^6)
Pseoducode:
vector<int> multiples[1000001];
void solve(vector<int> arr)
{
for (int i = 0; i < arr.size(); i++)
{
for (int j = 0; j < primefactor[arr[i]].size(); j++)
multiples[primefactor[arr[i]][j]].push_back(i);
if (arr[i] == 1)
multiples[1].push_back(i);
}
for (int i = 0; i < arr.size(); i++)
make_set(i);
for (int i = 1; i < 1000001; i++)
if (multiples[i].size() > 1)
for (int j = 1; j < multiples[i].size(); j++)
union_sets(multiples[i][j], multiples[i][j - 1]);
int ans = 0;
for (int i = 0; i < arr.size(); i++)
if (parent[i] == i)
ans++;
cout << ans << endl;
}
Sieve to find all prime factors:
vector<bool> isprime(1000001, true);
vector<int> primefactor[1000001];
void sieve()
{
isprime[0] = false;
isprime[1] = false;
for (int i = 2; i <= 1000000; i++)
if (isprime[i])
for (int j = i; j <= 1000000; j += i)
{
isprime[j] = false;
primefactor[j].push_back(i);
}
}
DSU:
int parent[100001];
int size[100001];
void make_set(int v)
{
parent[v] = v;
size[v] = 1;
}
int find_set(int v)
{
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b)
{
a = find_set(a);
b = find_set(b);
if (a != b)
{
if (size[a] < size[b])
swap(a, b);
parent[b] = a;
size[a] += size[b];
}
}
Entering edit mode
unordered_map<long double, long long> mp;
long long solve(vector<vector<int>> arr){
int n = arr.size();
long double angle;
long long count=0;
for(int i = 0;i<n; i++){
int x=arr[i][0],y=arr[i][1];
if(arr[i][0]) angle=(abs(y*1.0)/abs(x));
else angle=0.0;
mp[angle]++;
}
for(auto m:mp){
long long c = m.second; count+=(c*(c-1))/2;
}
return count;
}
int main() {
vector<vector<int>> arr;
arr={{1,2},{2,4},{3,6}};
int ans= solve(arr);
printf("%d",ans);
}
Entering edit mode
Question-2
Overview
- Given a string A consisting of N lowercase English alphabets.
- Consider a function that takes a character as an argument and returns the ASCII value of the character. For example f(a)=97, f(z)=122.
- For each index i (1 <= i <= N), determine the count of indices j such that j > i and |f(Ai)-f(Aj)| <= D.
- Here |x| denotes the absolute value of x.
- Return an array of n integers which denotes for each index i (1 <= i <= N), the count of indices j such that j > i and |f(Ai)-f(Aj)| <= D.
Solution
- Reverse the string.
- Now iterate from beginning to the end. As you move on increment the frequency of each character in a frequency array.
For the current character, before incrementing its frequency do the following
- Iterate over all possible characters from a to z. Denote it as previous_character.
- Now for each of them check if |f(current_character)-f(previous_character)|<=D .
- If yes then increment the answer for the current index by frequency[previous_character] otherwise proceed.
- Push the answer for the current index in a vector let's say v_ans.
- Now reverse the vector. This is the required vector that you need to print.
Code
ll n;
cin >> n;
string s;
cin >> s;
ll d;
cin >> d;
vector<ll> freq(26), vans;
for (ll i = n - 1; i >= 0; i--)
{
char ch = 'a';
ll ans = 0;
for (ll j = 0; j < 26; j++)
{
ch = 'a' + j;
if (abs(s[i] - ch) <= d)
{
ans += freq[(ch-'a')];
}
}
freq[s[i] - 'a']++;
vans.pb(ans);
}
reverse(all(vans));
for (auto it : vans)
{
cout << it << " ";
}
cout << endl;
return;
For Divisor Friends question
i think this solution works fine
```
#include <bits/stdc++.h>
using namespace std;
int minimumGroups(int n, vector<int> &arr)
{
int count = 0;
int maxi=INT_MIN;
for(int i=0;i<n;i++){
maxi=max(maxi,arr[i]);
}
// cout<<maxi<<endl;
vector<int> hash(maxi + 1, 0);
for (int i = 0; i < n; i++)
{
hash[arr[i]]++;
}
for (int i = 2; i <= maxi; i++)
{
int iter = i;
int temp = 0;
while (iter <= maxi)
{
if(hash[iter]==1){
temp=max(temp,1);
hash[iter]=2;
}
else if(hash[iter]==2){
temp=2;
}
iter += i;
}
// cout<<"at "<<i<<" temp is "<<temp<<endl;
if(temp==1){
count++;
}
}
return count;
}
int main()
{
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++)
cin >> arr[i];
int result = minimumGroups(n,arr);
cout<<result<<endl;
return 0;
}
```
i have taken an array where initially the values at the index equal to the values present in the given array is 1, we start from loop from 2, at some i , we are interating over all the multiples of i and in that if no multiple is added to any group before then we increasing the count and while iterating we are making the hash value of the multiples to 2 so that we can detect next time when we visit this number as the multiple of some other number
tested from [2,4,6,5] [2,4,6,5,9] [2,4,6,5,9,10] [2,3,6]
problem :- count function
#include <bits/stdc++.h>
using namespace std;
vector<int> d_distance(int n, string s, int d)
{
vector<int> result(n);
unordered_map<int, int> hash;
hash[s[n - 1] - '0']++;
for (int i = n - 2; i >= 0; i--)
{
int count = 0;
int temp = s[i] - '0';
for (int j = temp - d; j <= temp + d; j++)
{
if (hash.count(j))
{
count += hash[j];
}
}
hash[temp]++;
result[i] = count;
}
return result;
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
string s;
cin >> s;
int d;
cin >> d;
vector<int> result=d_distance(n, s, d);
for(int i=0;i<n;i++){
cout<<result[i]<<" ";
}
cout<<endl;
}
return 0;
}
iterating from the back and for every i iam checking how many numbers are there with in the range ascii(i)-d and ascii(i)+d, after that adding the current dealing char to the map, complexity will n*d(time)