12 months ago

Pratyush Agrawal • 0

Mumbai

Problem: Bits in Archie

#include <iostream>
#include <vector>

using namespace std;

// set bit = 1 , therefore need to count total number of 1's in the number
int countSetBits(int n) {
    int count = 0;
    // here we are checking if the number is greater than 0 or not
    // if it is greater than 0 then we will check if the last bit is set or not
    // if it is set then we will increment the count
    // then we will right shift the number by 1 bit
    // we will do this until the number is greater than 0
    // through this we will get the total number of set bits in the number
    while (n > 0) {
        count += n & 1; // here we are checking if the last bit is set or not, if set then increment count
        n >>= 1; // here we are right shifting the number by 1 bit
    }
    return count;
}

int countBit(vector<int>& arr, int k) {
    int n = arr.size();
    int count = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int bitwiseOR = arr[i] | arr[j];
            int bitwiseAND = arr[i] & arr[j];
            int totalSetBits = countSetBits(bitwiseOR) + countSetBits(bitwiseAND);

            if (totalSetBits >= k) {
                count++;
            }
        }
    }

    return count;
}

int main() {
    vector<int> arr = {3,1,9,8};
    int k = 3;

    int result = countBit(arr, k);
    cout << "Number of unordered pairs with sum of set bits >= " << k << ": " << result << endl;

    return 0;
}

Problem : Stable Segments

#include <iostream>

int CountStableSegments(int capacity[], int n) {
    int count = 0;

    for (int i = 0; i < n; ++i) {
        int sum = 0;
        for (int j = i + 1; j < n; ++j) {
            sum += capacity[j - 1];
            if (capacity[i] == capacity[j] && sum == capacity[i])
                ++count;
        }
    }

    return count;
}

int main() {
    int capacity[] = {9,3,3,3,9};
    int n = sizeof(capacity) / sizeof(capacity[0]);

    int stableSegments = CountStableSegments(capacity, n);
    std::cout << "Number of stable segments: " << stableSegments << std::endl;

    return 0;
}

Problem : Social Connections 

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

void dfs(int node, const vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

int countComponents(int totalNodes, const vector<int>& connectionsFrom, const vector<int>& connectionsTo) {
    vector<vector<int>> graph(totalNodes);
    for (int i = 0; i < connectionsFrom.size(); ++i) {
        graph[connectionsFrom[i] - 1].push_back(connectionsTo[i] - 1);
        graph[connectionsTo[i] - 1].push_back(connectionsFrom[i] - 1);
    }

    vector<bool> visited(totalNodes, false);
    int componentCount = 0;

    for (int i = 0; i < totalNodes; ++i) {
        if (!visited[i]) {
            dfs(i, graph, visited);
            ++componentCount;
        }
    }
    return componentCount;
}

int main() {
    int totalNodes = 7;
    vector<int> connectionsFrom = {1, 2, 3, 5};
    vector<int> connectionsTo = {2, 3, 4, 6};

    int components = countComponents(totalNodes, connectionsFrom, connectionsTo);
    cout << "Total different components: " << components << endl;

    return 0;
}