How should I practice Paint the Ceiling?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Snowflake online assessment problems in FastPrep.

Is Paint the Ceiling associated with Snowflake?

FastPrep tags this as a Snowflake online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Sorting

Paint the Ceiling

Learn this problem

● Medium

SnowflakeINTERNOA

See Snowflake hiring insights

Problem statement

You want to build yourself a house. The building company you hired can only build houses with sides from their specific set s. That means they can build you a square house or a rectangular one but if and only if its length and width belong to the sets.

This month, they have a special promotion: they will paint the ceiling of a new house for free... but only if its area is not more than a. You want them to do it for free but you also want to be sure that the house will be comfortable and not too small. How many possible house configurations can you create to have the ceiling painted for free given the side lengths offered?

There is a method to how the company decides what lengths of sides to produce. To determine n lengths of wall segments to offer, they start with a seed value s0, some variables k, b and m, and use the following equation to determine all other side lengths s_i:

s_i = (( k * s_{i-1} + b)mod m+1+s_{i-1}) for 1 <= i < n

Function

paintTheCeiling(s0: int, n: int, k: int, b: int, m: int, a: long) → long

Complete the function paintTheCeiling in the editor.

paintTheCeiling has the following parameters:

s0: an integer, the seed value for side lengths
n: an integer, the number of side lengths to produce
k: an integer
b: an integer
m: an integer
a: a long integer, the maximum area for a free paint job

Returns

long integer: the number of possible house configurations

Examples

Example 1

s0 = 2n = 3k = 3b = 3m = 2a = 15return = 5

Now that we have our set of lengths, we can brute force the solution using the following tests assuming a=15:

s=[2,4,6]

s1 s2 s1xs2 s1xs2≤a

2 2 4 True

2 4 8 True

2 6 12 True

4 2 8 True

4 4 16 False

4 6 24 False

6 2 12 True

6 4 24 False

6 6 36 False

There are 5 combinations that will result in a free paint job. Brute force will not meet the time constraints on large sets.

Constraints

1 ≤ n ≤ 6 x 10^6
1 ≤ s_i ≤ 10^9
1 ≤ k, b, m ≤ 10^9
1 ≤ a ≤ 10^18

Problem statement

Function

Examples

Example 1

Constraints

More Snowflake problems