#include <bits/stdc++.h>
using namespace std;

class UnionFind {
    vector<int> parent, rank;
    
public:
    UnionFind(int n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        rank.resize(n, 0);
    }
    
    int find(int u) {
        if (u != parent[u])
            parent[u] = find(parent[u]);
        return parent[u];
    }
    
    void unite(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            if (rank[rootU] > rank[rootV])
                parent[rootV] = rootU;
            else if (rank[rootU] < rank[rootV])
                parent[rootU] = rootV;
            else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }
};

int solve(int n, int c_service, int c_link, vector<pair<int, int>>& pairs) {
    UnionFind uf(n);

    for (auto& p : pairs) {
        uf.unite(p.first - 1, p.second - 1); 
    }

    vector<bool> conn(n, false);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int root = uf.find(i);
        if (!conn[root]) {
            conn[root] = true;
            cnt++;
        }
    }

    int op1 = n * c_service; 
    int op2 = cnt * c_service + (n - cnt) * c_link;

    return min(op1,op2);
}

int main() {
    int n, c_service, c_link, numPairs;
  
    cin >> n >> numPairs >> c_service >> c_link;

    vector<pair<int, int>> pairs(numPairs);

    for (int i = 0; i < numPairs; i++) {
        cin >> pairs[i].first >> pairs[i].second;
    }

    int minCost = solve(n, c_service, c_link, pairs);
    cout << minCost << endl;

    return 0;
}

IBM✅

#include <iostream>
using namespace std;

int solve(int a, int b) {
    long result = 1;
    long low = 1;
    long high = a;
    while (low <= high) {
        long mid = (low + high) / 2;
        if ((mid * (mid - 1)) / 2 <= b) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

IBM✅

🚀Hiring!!
Work From Home - Fresher

QA Engineer (Manual testing) who can join us immediately.

Eligiblity: Fresher

Interested candidates can share their cv on
himanshi@wizni.com

Company Name : NTT Data
Role : Associate Software Engineer
Batch : 2024/2023/2022 passouts

Link : https://careers.services.global.ntt/global/en/job/NTT1GLOBALR117718EXTERNALENGLOBAL/Associate-Software-Development-Engineer

#include <bits/stdc++.h>
using namespace std;

bool canForm(int m, int k) {
    return m >= k * (k - 1);
}

int solve(int n, int m) {
    int l = 1, r = n;
    int res = 1;

    while (l <= r) {
        int mid = l + (r - l) / 2;

        if (canForm(m, mid)) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    return res;
}

int main() {
    int n, m;
    cin >> n >> m;

    int ans = solve(n, m);
    cout << ans<< endl;

    return 0;
}

IBM✅

Jade Global is organising a Walkin Interview for 2024 Graduates (No Post-Graduates) ❤️❤️❤️

Stream:
BSc (CS / IT / Stats / Maths / Physics / Electronics)
BCA
BBA-CA (Freshers)

Year of passing: 2024
60% Overall.

Joining: By Mid September

Opportunities
1. Sponsered MSc and MTech Degree from BITS Pilani.
2. Technical and Self- Development Program.

Drive: Monday to Friday (Coming Week) from 10 AM to 12 Noon.

Venue: Wadgaonsheri Office, Nyati Tech Park, 7th Floor, Near Brahma Suncity, Behind Nyati Meadows, Wadgaon Sheri Pune- 411014

Company Name: Clearfeed
Role: Software Engineer Intern

Batch eligible: 2025 grads only

Apply: https://clearfeed.keka.com/careers/jobdetails/150

Company Name: Akamai Technology

Role: Software Engineer (Remote)
Batch eligible: 2023 and 2024 grads

Apply: https://akamaicareers.inflightcloud.com/jobdetails/aka_ext/035360

Amgen is hiring Associate Software Engineer

For 2021, 2022, 2023, 2024 grads
Location: Hyderabad

https://careers.amgen.com/en/job/hyderabad/associate-software-engineer/87/68552403264

https://x.com/Arpitaaa01/status/1822328904599880063?t=pL-Cb2_RoxUz6JRQBqVGiw&s=35

Myntra Referral form :

https://docs.google.com/forms/d/e/1FAIpQLSeHEIZDYx5OxiFAVplcZc3DIw_-t43XKnuThLSZGQbyeJNv2w/viewform

#include <iostream>
#include <vector>
#include <deque>
#include <climits>
#include <algorithm>

int solve(int N, int K, const std::vector<int>& houses) {
    vector<int> indices(N);
    for (int i = 0; i < houses.size(); i++) {
        indices[houses[i] - 1] = i + 1;
    }

deque<int> maxDeque;
    int ans = INT_MAX;

    for (int i = 0; i < K; i++) {
        while (!maxDeque.empty() && indices[i] >= indices[maxDeque.back()]) {
            maxDeque.pop_back();
        }
        maxDeque.push_back(i);
    }

    ans = indices[maxDeque.front()];

    for (int i = K; i < N; i++) {
        if (maxDeque.front() <= i - K) {
            maxDeque.pop_front();
        }
        while (!maxDeque.empty() && indices[i] >= indices[maxDeque.back()]) {
            maxDeque.pop_back();
        }
        maxDeque.push_back(i);

        ans = std::min(ans, indices[maxDeque.front()]);
    }

    return ans;
}

.

UC Happy Neighborhood ✅

def solve(N, M, K, arr):
    target_avg = K / N
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i + 1] = prefix_sum[i] + arr[i]
    
    def checkPerm():
        score = 0
        for i in range(N):
            if score / (i + 1) < target_avg:
                score += M
            elif score / (i + 1) > target_avg:
                return False
        return score / N == target_avg
    
    def averageScore(index, currSum):
        if index == N:
            return currSum == K
        
        for i in range(index, N):
            arr[index], arr[i] = arr[i], arr[index]
            if currSum + arr[index] <= K and averageScore(index + 1, currSum + arr[index]):
                return True
            arr[index], arr[i] = arr[i], arr[index]
        
        return False

    if checkPerm() or averageScore(0, 0):
        return "NO"
    return "YES"

Average score GE ✅

def solve(start, stop):
    def isPerfect(num):
        original = num
        while num > 0:
            digit = num % 10
            if digit == 0 or original % digit != 0:
                return False
            num //= 10
        return True

    perfSum = 0
    for num in range(start, stop + 1):
        if isPerfect(num):
            perfSum += num
    
    return perfSum

Perfect number
Motorq ✅

import math

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(math.sqrt(n)) + 1):
        if primes[i]:
            for j in range(i * i, n + 1, i):
                primes[j] = False
    return primes

def least_prime_factor(n, primes):
    for i in range(2, n + 1):
        if primes[i] and n % i == 0:
            return i
    return n

def divisor_queries(N, Q, a, queries):
    max_val = max(max(a), 10**6)
    primes = sieve_of_eratosthenes(max_val)
    
    results = []
    for query in queries:
        query_type = query[0]
        
        if query_type == 1:
            l, r = query[1], query[2]
            for i in range(l - 1, r):
                lpf = least_prime_factor(a[i], primes)
                a[i] //= lpf
        
        elif query_type == 2:
            l, r = query[1], query[2]
            sum_range = sum(a[l-1:r])
            results.append(sum_range)
        
        elif query_type == 3:
            i, k = query[1], query[2]
            a[i-1] = k
    
    return results

Least prime factor ✅

#include <bits/stdc++.h>
using namespace std;
vector<int> suffixArray(const string& s) {
    int n = s.size();
    vector<int> p(n), c(n);
    vector<pair<char, int>> a(n);
    for (int i = 0; i < n; i++) a[i] = {s[i], i};
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) p[i] = a[i].second;
    c[p[0]] = 0;
    for (int i = 1; i < n; i++) {
        if (a[i].first == a[i - 1].first) {
            c[p[i]] = c[p[i - 1]];
        } else {
            c[p[i]] = c[p[i - 1]] + 1;
        }
    }
    int k = 0;
    vector<int> pn(n), cn(n);
    while ((1 << k) < n) {
        for (int i = 0; i < n; i++) {
            pn[i] = p[i] - (1 << k);
            if (pn[i] < 0) pn[i] += n;
        }
        vector<int> cnt(n);
        for (int x : c) cnt[x]++;
        for (int i = 1; i < n; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) p[--cnt[c[pn[i]]]] = pn[i];
        cn[p[0]] = 0;
        for (int i = 1; i < n; i++) {
            pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << k)) % n]};
            pair<int, int> prev = {c[p[i - 1]], c[(p[i - 1] + (1 << k)) % n]};
            if (cur == prev) {
                cn[p[i]] = cn[p[i - 1]];
            } else {
                cn[p[i]] = cn[p[i - 1]] + 1;
            }
        }
        c.swap(cn);
        k++;
    }
    return p;
}

vector<int> lcpArray(const string& s, const vector<int>& p) {
    int n = s.size();
    vector<int> rank(n), lcp(n - 1);
    for (int i = 0; i < n; i++) rank[p[i]] = i;
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] == n - 1) {
            k = 0;
            continue;
        }
        int j = p[rank[i] + 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        lcp[rank[i]] = k;
        if (k > 0) k--;
    }
    return lcp;
}

int substringCalculator(const string& s) {
    string s_ext = s + "$";
    vector<int> p = suffixArray(s_ext);
    vector<int> lcp = lcpArray(s_ext, p);
    long long total = 0;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        total += lcp[i];
    }
    return (long long)n * (n + 1) / 2 - total;
}

int main() {
    string s;
    cin >> s;
    cout << substringCalculator(s) << endl;
    return 0;
}

substringCalculator ✅

public static int maximumLearning(List<Integer> iv, List<Integer> articles, int p) {
  int size = articles.size();
  int[] art = new int[size];
  int[] ivs = new int[size];
for(int i=0;i<size;i++){
   art[i] = articles.get(i)*2;
   ivs[i] = iv.get(i);
}
return knapSackTopDownCode(ivs, art, p, size) ;
}
public static int knapSackTopDownCode(int[] val, int[] wt, int W, int n) {
   int mat[][] = new int [n+1][W+1];
   for(int i=1;i<n+1;i++) {
     for(int j=1;j<W+1;j++) {
          if(i==0 || j ==0)
              mat[i][j] =0;
          else if(wt[i-1]<=j) {
              mat[i][j] = Math.max(val[i-1]+ mat[i-1][j-wt[i-       1]],mat[i-1][j]);
           }
          else {
              mat[i][j] = mat[i-1][j];}
             }
       }
   return mat[n][W];
}
}

maximumLearning✅