FastPrep
Problem · Breadth First Search

Minimum Steps to Achieve Target State

Learn this problem
● HardCiscoFULLTIMEOA
See Cisco hiring insights

Problem statement

Given 4 Jugs namely [J1, J2, J3, J4] with capacities [C1, C2, C3, C4] and initial water content as [S1, S2, S3, S4]. Determine how many steps are needed to achieve the final state of [F1, F2, F3, F4] by transferring water from one jug to another without losing any water.

Input:

Total number of entries = 13

  • First line specifies the number of entries in the array, which is 12 in our case
  • Next 4 lines contain the capacities of the 4 jugs
  • Next 4 lines contain the initial content of the 4 jugs
  • Next 4 lines contain the final content of the 4 jugs

    • Output:

    The minimum number of steps required to reach Final State (F) from Initial State (S).

    Return -1 if not possible.

    Function

    minStepsToAchieveTargetState(capacities: int[], initial: int[], target: int[]) → int

    Examples

    Example 1

    capacities = [12, 13, 12, 10]initial = [6, 6, 0, 0]target = [12, 0, 0, 0]return = 1

    In one step, we can transfer 6 units of water from J1 and J2 to J3, achieving the final state of [12, 0, 0, 0].

    Constraints

    0 < Ci <= 500 for each i: [1,4]
    0 < Si, Fi <= Ci for each i: [1,4]
    Sum(Si) = Sum(Fi)

    More Cisco problems

    drafts saved locally
    public int minStepsToAchieveTargetState(int[] capacities, int[] initial, int[] target) {
  // write your code here
}
    capacities[12, 13, 12, 10]
    initial[6, 6, 0, 0]
    target[12, 0, 0, 0]
    expected1
    checking account