Tap here to switch tabs
Problem
Submissions

Problem: Minimum Generations to Target Point

Minimum Generations to Target Point starts with distinct 3D points and repeatedly averages pairs by flooring each coordinate. Return the earliest generation containing the target, or -1 if impossible.

Statement

You are given an array points, where each element points[i] =[xi,yi,zi]= [x_i, y_i, z_i] represents a point in three dimensional space, and an array target representing a target point.

At generation 00, the set of available points consists of all coordinates in points.

In each subsequent generation k≥1k \geq 1, a new point can be produced from any pair of distinct points p1=[x1,y1,z1]p_1 = [x_1, y_1, z_1] and p2=[x2,y2,z2]p_2 = [x_2, y_2, z_2] currently present in the set of available points. The coordinates of the new point are given by:

pnew=[⌊x1+x22⌋,⌊y1+y22⌋,⌊z1+z22⌋]p_{new} = \left[\left\lfloor \frac{x_1 + x_2}{2} \right\rfloor, \left\lfloor \frac{y_1 + y_2}{2} \right\rfloor, \left\lfloor \frac{z_1 + z_2}{2} \right\rfloor\right]

Return the minimum generation kk at which target becomes available. If target can never be produced, return -1.

Constraints:

  • 1<=1 <= points.length <=20<= 20

  • points[i].length ==3== 3

  • 0 <= points[i][j] <=6<= 6

  • target.length ==3== 3

  • 0 <= target[i] <=6<= 6

  • All points[i] are distinct.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Generations to Target Point

Minimum Generations to Target Point starts with distinct 3D points and repeatedly averages pairs by flooring each coordinate. Return the earliest generation containing the target, or -1 if impossible.

Statement

You are given an array points, where each element points[i] =[xi,yi,zi]= [x_i, y_i, z_i] represents a point in three dimensional space, and an array target representing a target point.

At generation 00, the set of available points consists of all coordinates in points.

In each subsequent generation k≥1k \geq 1, a new point can be produced from any pair of distinct points p1=[x1,y1,z1]p_1 = [x_1, y_1, z_1] and p2=[x2,y2,z2]p_2 = [x_2, y_2, z_2] currently present in the set of available points. The coordinates of the new point are given by:

pnew=[⌊x1+x22⌋,⌊y1+y22⌋,⌊z1+z22⌋]p_{new} = \left[\left\lfloor \frac{x_1 + x_2}{2} \right\rfloor, \left\lfloor \frac{y_1 + y_2}{2} \right\rfloor, \left\lfloor \frac{z_1 + z_2}{2} \right\rfloor\right]

Return the minimum generation kk at which target becomes available. If target can never be produced, return -1.

Constraints:

  • 1<=1 <= points.length <=20<= 20

  • points[i].length ==3== 3

  • 0 <= points[i][j] <=6<= 6

  • target.length ==3== 3

  • 0 <= target[i] <=6<= 6

  • All points[i] are distinct.