Question: SAP Labs, Recently Asked Questions in IIT-G for On-Campus Assessments, November, 2022
1
Entering edit mode

# Question 2

## Count Function

1
Entering edit mode
``````unordered_map&lt;long double, long long&gt; mp;
long long solve(vector&lt;vector&lt;int&gt;&gt; arr){
int n = arr.size();
long double angle;
long long count=0;
for(int i = 0;i&lt;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&lt;vector&lt;int&gt;&gt; arr;
arr={{1,2},{2,4},{3,6}};
int ans= solve(arr);
printf("%d",ans);
}
``````
0
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*20`
• `10^6` no of numbers
• 20, because `2^20 &gt; 10^6`
• Exact count is `2853708.`
• For all primes `i`, store the indices of elements in the given array which are its multiples in multiples[i].
• This would take `N*20`at max
• Stores indices of `A[j] =1` in `multiples[1]`
• Now go to each prime number `i &lt; 10^6` and connect the adjacent elements in the `multiples[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 `multiples` list , 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]=i` in the dsu

`Complexity`

• `O(NLOGN+10^6log10^6)`

`Pseoducode:`

``````vector&lt;int&gt; multiples[1000001];
void solve(vector&lt;int&gt; arr)
{
for (int i = 0; i &lt; arr.size(); i++)
{
for (int j = 0; j &lt; 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 &lt; arr.size(); i++)
make_set(i);

for (int i = 1; i &lt; 1000001; i++)
if (multiples[i].size() &gt; 1)
for (int j = 1; j &lt; multiples[i].size(); j++)
union_sets(multiples[i][j], multiples[i][j - 1]);

int ans = 0;
for (int i = 0; i &lt; arr.size(); i++)
if (parent[i] == i)
ans++;
cout &lt;&lt; ans &lt;&lt; endl;
}
``````

`Sieve to find all prime factors:`

``````vector&lt;bool&gt; isprime(1000001, true);
vector&lt;int&gt; primefactor[1000001];
void sieve()
{
isprime[0] = false;
isprime[1] = false;
for (int i = 2; i &lt;= 1000000; i++)
if (isprime[i])
for (int j = i; j &lt;= 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] &lt; size[b])
swap(a, b);
parent[b] = a;
size[a] += size[b];
}
}
``````
0
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 &gt;&gt; n;
string s;
cin &gt;&gt; s;
ll d;
cin &gt;&gt; d;
vector&lt;ll&gt; freq(26), vans;
for (ll i = n - 1; i &gt;= 0; i--)
{
char ch = 'a';
ll ans = 0;
for (ll j = 0; j &lt; 26; j++)
{
ch = 'a' + j;
if (abs(s[i] - ch) &lt;= d)
{
ans += freq[(ch-'a')];
}
}
freq[s[i] - 'a']++;
vans.pb(ans);
}
reverse(all(vans));
for (auto it : vans)
{
cout &lt;&lt; it &lt;&lt; " ";
}
cout &lt;&lt; endl;
return;
``````
0
Entering edit mode