Bricks and Building

An old planet called Alpha has been found but it is destructed completely. Archaeologists after the expedition found a map that depicts all the buildings that were in Alpha. In the map following facts were stated:

• Buildings were made of identical bricks and all the bricks were equal-sized.
• All the buildings and bricks were 2D rectangles of some height and an equal width.
• A building is formed by putting bricks one on the another. The height of the building is the sum of the heights of bricks. None of the bricks used are ever broken or rotated.

Now you have q queries.

Each query contains an integer k. For every query, you have to print the count of buildings that can be made if you had an infinite number of bricks of size k adhering to the above rules.

Example:

Input:  n = 4, arr = {5, 8, 10, 8}, q = 1,queries = {2}
Output: 3

Approach

C++

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

int a[100005], f[100005];

void bricksAndBuildind(int n, vector<int> &arr,
                       int q, vector<int> &queries)
{
    for (int i = 0; i < n; i++)
    {

        a[arr[i]]++;
    }
    f[1] = n;
    int cnt, val;
    for (int j = 2; j <= 100000; j++)
    {
        val = 0;
        cnt = 1;
        while (j * cnt <= 100000)
        {
            val += a[j * cnt];
            cnt++;
        }
        f[j] = val;
    }

    for (int j = 0; j < q; j++)
    {
        int k = queries[j];
        cout << f[k] << '\n';
    }
}
int main()
{

    int n = 4;
    vector<int> arr = {5, 8, 10, 8};
    int q = 1;
    vector<int> queries = {2};

    bricksAndBuildind(n, arr, q, queries);

    return 0;
}