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

Question 1

Click here to Practice

Divisor Friends

Sap Labs1.2Sap Labs1.2

Question 2

Click here to Practice

Count Function

Sap Labs 2.1Sap Labs 2.2

ADD COMMENTlink 18 days ago John 450 • updated 17 days ago QWERTY474 • 40
1
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);
}
ADD COMMENTlink 17 days ago QWERTY474 • 40
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 is10^6*20
      • 10^6 no of numbers
      • 20, because 2^20 > 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*20at max
    • Stores indices of A[j] =1 in multiples[1]
  • Now go to each prime number i < 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<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];
    }
}
ADD COMMENTlink 18 days ago Lokesh 230
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;
ADD COMMENTlink 17 days ago Ujjwal Srivastava 160
0
Entering edit mode

enter image description here

ADD COMMENTlink 17 days ago QWERTY474 • 40

Login before adding your answer.

Similar Posts
Loading Similar Posts