Number of subsets with product less than or equals to K | Recently Asked in Morgan Stanley

Solve this question on our practice portal:

𝙁𝙤𝙡𝙡𝙤𝙬 𝙪𝙨 𝙤𝙣 𝙤𝙪𝙧 𝙎𝙤𝙘𝙞𝙖𝙡 𝙈𝙚𝙙𝙞𝙖 𝙃𝙖𝙣𝙙𝙡𝙚𝙨 -

[rabindrapatra]

where this is used in company production in last 10 years.

[nikkimittal]

sir how we calculated the product of elements and pushed them into subset1 and subset2 that i was able to get otherwise sir it was really helpful

[MyOneFiftiethOfADollar]

maybe would have been better to start with an arbitrary K, say 11, and then exhaustively checking the product of each of the 16 subsets, listing the ones that had product <= 11. I guess empty set has "product" = 0 or do you just ignore it?

[MilindGupta]

I am not getting why you guys uploading a bigger stream of the same question where u have discussed this in very detail but now it's deleted why?

[omkarpachore]

I have some doubts:
1. Why in example 1 there's no (3, 3).
2. How single elements give product less than 12 as there's no 1 in given elements.

[abidalinu]

What is the time and space complexity of this time? if it's in N^2, it can be done in a few lines as below:

public static int NumberOfSubsets(int[] arr, int k)
{
int numberOfSubsts = 0;

Console.Write("Subsets are:");

for (int i = 0; i < arr.Length; i++)
{
if (i <= k)
{
Console.Write($" ({arr[i]}), ");
numberOfSubsts++;
}

for (int j = i+1; j < arr.Length; j++)
{
if (arr[i] * arr[j] <= k)
{
Console.Write($" ({arr[i]}, {arr[j]}), ");
numberOfSubsts++;
}
}
}

return numberOfSubsts;
}