Counting Arrays with divisibility constraint

By Ann Roberts On May 9, 2023

Given two integers X and Y, the task is to find the number of different arrays that can be constructed of size largest possible size that follow the conditions below:

Every element of the array should not be less than X and should not be greater than Y.
Every element should occur at most once in the array.
Let A_iand A_j be two elements of the array where i is not equal to j, Then A_ishould divide A_j or A_j should divide A_i.

Note: Two arrays will be considered different if at least one element is present in the first array but not in the second one.

Examples:

Input: X = 3, Y = 8
Output: 2
Explanation: 2 arrays of the largest possible size two can be constructed, and the array are {3, 6} and {4, 8}.

Input: X = 2, Y = 62
Output: 6
Explanation: 6 arrays can be constructed of the largest possible size five and arrays are {2, 4, 8, 16, 32}, {3, 6, 12, 24, 48}, {2, 4, 8, 16, 48}, {2, 6, 12, 24, 48}, {2, 4, 12, 24, 48} and {2, 4, 8, 24, 48}.

Approach: To solve the problem follow the below idea:

The largest size of the array can be calculated by { 2⁰X, 2¹*X, 2²*X……} till the element is less than or equal to Y.This will be the largest possible size of the array because if we multiply by 1, the element will become the same and if multiple by 3, array size decreases.

We will use Binary search and find in the search range from X to Y, and we will find the highest value of mid such that we can make an array of the largest size if our first element is mid and assign pos1 = mid. But we can also multiply by 3 at most once at any place of 2¹, 2²…, because we if multiply 3 two times, it will reduce array size, instead we can multiply 2 three times which is better 2*2*2<3*3. Using binary search, we can find the highest value of mid such that we can make an array of the largest size if our first element is mid and we can place 3 in any of these positions 2¹, 2².. and we can place 3 anywhere from a₂ to a_n and assign pos2 = mid. So, Our Final answer will be (pos1-X+1)+(n-1)*(pos2-X+1), where n is the largest possible size of the array..

Below are the steps to implement the approach:

First find the largest possible size of the array by doing a run while loop { 2⁰X, 2¹*X, 2²*X……} till the element is less than or equal to Y and every time increase the largest size by 1
Using Binary search, find in the search range from X to Y, we will find the highest value of mid such that we can make an array of the largest size if our first element is mid and assign pos1 = 3.
Using binary search, find in search range from X to Y, we can find the highest value of mid such that we can make an array of largest size if our first element is mid and we can place 3 in any of these positions 2¹, 2²… and assign
pos2 = mid.
The answer will be (pos1-X+1)+(n-1)*(pos2-X+1), where n is the largest possible size of the array.
Finally, return the answer.

Below is the code for the above approach:

C++

// C++ code for the above approach:

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

// Function to find find the number of
// different arrays can be construct
// of size largest possible size
int largestsizearrays(int x, int y)
{
    int pos1, pos2 = -1, lsize = 0;
    int l = x, r = y;

    // Finding largest possible
    // size of array
    while (l <= r) {
        l *= 2;

        // Increasing size by 1 every time
        lsize += 1;
    }

    l = x;
    r = y;
    int mid;

    while (l <= r) {

        // Calculating mid
        mid = l + (r - l) / 2;
        int temp = pow(2, lsize - 1);
        temp *= mid;

        // If temp is less than or equal
        // to y, then search in
        if (temp <= y) {
            pos1 = mid;

            // right of mid
            l = mid + 1;
        }

        // left of mid
        else {
            r = mid - 1;
        }
    }

    l = x;
    r = pos1;

    if (lsize >= 2) {
        while (l <= r) {
            mid = l + (r - l) / 2;
            int temp = pow(2, lsize - 2);
            temp *= mid;
            temp *= 3;

            // If temp is less than or
            // equal to y, then search in
            if (temp <= y) {
                pos2 = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
    }

    // Storing answer
    int ans = 0;
    ans += (pos1 - x + 1);
    if (pos2 != -1) {
        ans += (pos2 - x + 1) * (lsize - 1);
    }

    // Finally return the answer
    return ans;
}

// Drive code
int main()
{
    int x = 2, y = 62;

    // Function call
    cout << largestsizearrays(x, y);

    return 0;
}

Time Complexity: O(Log₂N), where N = Y-X
Auxiliary Space: O(1)

Last Updated :
08 May, 2023

Like Article

Save Article