Skip to main content
Talentd

Minimum Generations to Target Point - Solution & Explanation

MediumArrayHash TableSimulation5 min read
Practice this problem

Problem Statement

You are given a 2D integer array points where points[i] = [xi, yi, zi] represents a point in 3D space, and an integer array target representing a target point.

Define generation 0 as the initial list of points. For each integer k >= 1, form generation k as follows:

  • Consider every pair of two distinct points a = [x1, y1, z1] and b = [x2, y2, z2] taken from all points produced in generations 0 through k - 1.
  • For each such pair, compute c = [floor((x1 + x2) / 2), floor((y1 + y2) / 2), floor((z1 + z2) / 2)] and collect every such c into a generation k.
  • All points in the generation k are produced simultaneously from points in generations 0 through​​​​​​​ k - 1.
  • After generation k is formed, the points in the generation k are considered available for forming later generations.

Return the smallest integer k such that the target appears in one of the generations 0 through k. If the target is already in the initial points, return 0. If it is impossible to obtain the target, return -1.

Notes:

  • floor denotes rounding down to the nearest integer.
  • "Two distinct points" means the two chosen points must have different (x, y, z) coordinates. A point cannot be paired with itself, and pairing two points with identical coordinates is not possible.

 

Example 1:

Input: points = [[0,0,0],[6,6,6]], target = [3,3,3]

Output: 1

Explanation:

  • Generation 0: The initial points = [[0, 0, 0], [6, 6, 6]].
  • The target = [3, 3, 3] does not exist in generation 0.
  • Generation 1: For each pair of points in generation 0, we create new points.
    • Using [0, 0, 0] and [6, 6, 6], we generate [3, 3, 3].
  • After generation 1, points = [[0, 0, 0], [6, 6, 6], [3, 3, 3]].
  • The target = [3, 3, 3] is found in generation 1, so the smallest k is 1.

Example 2:

Input: points = [[0,0,0],[5,5,5]], target = [1,1,1]

Output: 2

Explanation:

  • Generation 0: The initial points = [[0, 0, 0], [5, 5, 5]].
  • The target = [1, 1, 1] does not exist in generation 0.
  • Generation 1: For each pair of points in generation 0, we create new points.
    • Using [0, 0, 0] and [5, 5, 5], we generate [2, 2, 2].
  • After generation 1, points = [[0, 0, 0], [5, 5, 5], [2, 2, 2]].
  • Generation 2: For each pair of points available after generation 1, we create new points.
    • Using [0, 0, 0] and [5, 5, 5], we generate [2, 2, 2].
    • Using [0, 0, 0] and [2, 2, 2], we generate [1, 1, 1].
    • Using [5, 5, 5] and [2, 2, 2], we generate [3, 3, 3].
  • After generation 2, points = [[0, 0, 0], [5, 5, 5], [2, 2, 2], [1, 1, 1], [3, 3, 3]].
  • The target = [1, 1, 1] is found in generation 2, so the smallest k is 2.

Example 3:

Input: points = [[0,0,0],[2,2,2],[3,3,3]], target = [2,2,2]

Output: 0

Explanation:

  • Generation 0: The initial points = [[0, 0, 0], [2, 2, 2], [3, 3, 3]].
  • The target = [2, 2, 2] already exists in generation 0, so the smallest k is 0.

Example 4:

Input: points = [[1,2,3]], target = [5,5,5]

Output: -1

Explanation:

  • Only one initial point is available, so no new points can be generated.
  • Therefore, the target cannot be obtained, and the answer is -1.

 

Constraints:

  • 1 <= points.length <= 20
  • points[i] = [xi, yi, zi​​​​​​​]
  • 0 <= xi, yi, zi <= 6
  • target.length == 3
  • ​​​​​​​0 <= target[i] <= 6
  • The initial set of points contains no duplicates.

Approach Overview

Problem Overview: You start at point (1,1). In one generation you can transform (x, y) into either (x + y, y) or (x, x + y). Given a target point (tx, ty), determine the minimum number of generations required to reach it, or return -1 if it is impossible.

Approach 1: Breadth‑First Search (Exponential)

Start from (1,1) and simulate every possible generation using BFS. Each state generates two children: (x + y, y) and (x, x + y). Stop when the target appears. While this guarantees the minimum generations, the search space grows extremely fast because coordinates increase every step. Time complexity is O(2^g) where g is the number of generations, and space complexity is also O(2^g) due to the queue.

Approach 2: Reverse Subtraction Simulation (O(max(tx, ty)))

Instead of building forward from (1,1), work backward from the target. If the last move produced (tx, ty), then one of the coordinates must have been the sum of the other and its previous value. That means the previous state was either (tx - ty, ty) or (tx, ty - tx). Repeatedly subtract the smaller coordinate from the larger until you reach (1,1). This mirrors the idea behind the greedy reduction used in the Euclidean algorithm. Time complexity is O(max(tx, ty)) in the worst case with O(1) space.

Approach 3: Greedy with Modulo Optimization (O(log n))

The subtraction process can be accelerated using a mathematical observation. If tx > ty, the previous value of tx must be tx % ty after multiple reverse steps. Instead of subtracting ty repeatedly, jump directly using the modulo operation. Continue reducing the larger coordinate until one becomes 1. When one coordinate is 1, the remaining generations are simply the difference in the other coordinate. This turns the process into a variant of the Euclidean GCD algorithm, commonly seen in math and greedy interview problems. Time complexity becomes O(log(max(tx, ty))) with O(1) space.

Recommended for interviews: Start by describing the brute force BFS to show understanding of the state transitions. Then pivot to the reverse greedy strategy. Interviewers usually expect the modulo‑optimized version because it reduces the process to a Euclidean‑style reduction with O(log n) time and constant space.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Breadth-First SearchO(2^g)O(2^g)Conceptual understanding of state transitions; impractical for large targets
Reverse SubtractionO(max(tx, ty))O(1)When demonstrating the reverse construction idea without optimization
Greedy with Modulo (Euclidean Reduction)O(log n)O(1)Optimal solution for large coordinates; expected interview answer

Video Solution

Leetcode 3923 | Minimum Generations to Target Point | Leetcode biweekly contest 182 • CodeWithMeGuys • 359 views views

Frequently Asked Questions

Is Minimum Generations to Target Point easy or hard?
The problem is typically rated Medium. The forward simulation is straightforward, but identifying the reverse greedy reduction with modulo optimization requires recognizing its similarity to the Euclidean GCD algorithm.
Minimum Generations to Target Point Python/Java solution
Most implementations use a loop that repeatedly reduces the larger coordinate using modulo operations until reaching (1,1) or determining the state is impossible. The same logic translates directly across Python, Java, and C++ because it relies only on integer arithmetic.
How to solve Minimum Generations to Target Point in O(log n)?
Start from the target point (tx, ty) and repeatedly reduce the larger coordinate using modulo: if tx > ty, set tx = tx % ty; otherwise set ty = ty % tx. Count how many reductions are performed. Once one coordinate becomes 1, the remaining generations equal the difference in the other coordinate.
What is the best approach for Minimum Generations to Target Point?
The optimal approach works backward from the target using a greedy reduction similar to the Euclidean algorithm. Instead of repeatedly subtracting the smaller coordinate, use the modulo operation to jump multiple steps at once. This reduces the time complexity to O(log(max(tx, ty))) with constant space.
Is Minimum Generations to Target Point asked at Google/Amazon/Meta?
This style of problem frequently appears in interviews at companies like Google and Amazon because it combines greedy reasoning with number theory concepts similar to the Euclidean algorithm. Variants are also seen in competitive programming and algorithmic screening rounds.
What data structure is used in Minimum Generations to Target Point?
The optimal solution does not rely on complex data structures. It uses simple integer arithmetic and greedy reduction. A queue may appear in the brute force BFS approach, but the efficient solution only tracks two integers.
What is the time complexity of Minimum Generations to Target Point?
The optimal greedy solution runs in O(log(max(tx, ty))) time because each step reduces one coordinate using a modulo operation similar to the GCD algorithm. Space complexity is O(1) since only a few integer variables are maintained.

Ready to solve this problem?

Practice Minimum Generations to Target Point with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays