Here in this blog, the Move weighting scale alternates under given constraints, and we are given a scale of positive weights with a limitless supply of each weight and an array of positive weights. Our objective is to place weights on the scale's left and right pans one at a time in such a way that the pans move to the side where the weight is placed, or the scale's pans should move to alternate sides each time. There are some constraints that are included with this problem statement. We are handed another integer, or "steps," that we must use to complete this procedure.
Another restriction is that we can't use the same weight twice, therefore if weight w is taken, we can't use it again in the following phase while applying weight to the opposite pan.
Sample Example
Let us understand this problem statement with the help of an example:
In move weighting scale alternate under given constraints, supposed we have weight array as 7,11 and we are also given some steps which are 3. Now we have to put the weight alternatively on the scale. And this needs to be kept in mind that we can't put the same weight in the same order on each scale. E.g. we can put 7 on the right scale and then on the next turn 7 on the left scale. So here we can put weight in sequences 7, 11, and 7 as there are 3 steps given. So the weights should be kept in the following order in order to move the scale alternately: 7, 11, 7.
Algorithm
Step 1: For the solution, we navigate through different DFS states, where each DFS state corresponds to the actual value of the difference between the left and right pans and the current step count.
Step 2: The difference in residue value will be stored, and the weight value that is chosen each time must be more than this difference and cannot be the same as the weight value that was previously chosen.
Step 3: If it is, we go one more step and recursively run the DFS Algorithm procedure with a fresh difference value.
Let us see the implementation of this approach in the next section of this blog.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
// DFS method to traverse among states of weighing scales
bool dfs(int residue, int curStep, int wt[], int arr[],
int N, int steps)
{
if (curStep > steps)
return true;
for (int i = 0; i < N; i++)
{
//weight is greater than current residue and not same as previous one
if (arr[i] > residue && arr[i] != wt[curStep - 1])
{
wt[curStep] = arr[i];
if (dfs(arr[i] - residue, curStep + 1, wt,
arr, N, steps))
return true;
}
}
return false; //if weight is not possible
}
void printWeights(int arr[], int N, int steps)
{
int wt[steps];
if (dfs(0, 0, wt, arr, N, steps))
{
for (int i = 0; i < steps; i++)
cout << wt[i] << " ";
cout << endl;
} else
cout << "Sequence is not possble\n";
}
int main()
{
int arr[] = {7,11};
int N = sizeof(arr) / sizeof(int);
int steps = 3;
cout << "The sequence is: " << endl;
printWeights(arr, N, steps);
return 0;
}
You can also try this code with Online C++ Compiler
class Graph
{
// DFS method to traverse among states of weighing scales
static boolean dfs(int residue, int curStep,
int[] wt, int[] arr,
int N, int steps)
{
if (curStep >= steps)
return true;
for (int i = 0; i < N; i++)
{
//weight is greater than current residue and not same as previous one
if (curStep - 1 < 0 ||
(arr[i] > residue &&
arr[i] != wt[curStep - 1]))
{
wt[curStep] = arr[i];
if (dfs(arr[i] - residue, curStep + 1,
wt, arr, N, steps))
return true;
}
}
return false; //if weight is not possible
}
static void printWeightOnScale(int[] arr,
int N, int steps)
{
int[] wt = new int[steps];
if (dfs(0, 0, wt, arr, N, steps))
{
for (int i = 0; i < steps; i++)
System.out.print(wt[i] + " ");
System.out.println();
} else
System.out.println("Sequence is not possble");
}
public static void main(String[] args)
{
int[] arr = {7,11
};
int N = arr.length;
int steps = 3;
System.out.println("The sequence is: ");
printWeightOnScale(arr, N, steps);
}
}
You can also try this code with Online Java Compiler
def dfs(residue, curStep, wt, arr, N, steps):
if (curStep >= steps):
return True
for i in range(N):
if (arr[i] > residue and
arr[i] != wt[curStep - 1]):
wt[curStep] = arr[i]
if (dfs(arr[i] - residue, curStep + 1,
wt, arr, N, steps)):
return True
# if any weight is not possible
return False
def printWeightsOnScale(arr, N, steps):
wt = [0] * (steps)
if (dfs(0, 0, wt, arr, N, steps)):
for i in range(steps):
print(wt[i], end = " ")
else:
print("Sequence is not possble")
if __name__ == '__main__':
arr = [7,11]
N = len(arr)
steps = 3
print("The sequence is: ")
printWeightsOnScale(arr, N, steps)
You can also try this code with Online Python Compiler
Let us analyze the time and complexity of this approach.
Complexity analysis
Time complexity
This approach will have the time complexity of the BFS algorithm which is O(V+E).
Frequently Asked Questions
What Is Graph Traversal?
The act of going over each vertex and edge of a graph at least once is known as graph traversal. It's crucial to consider the vertices' visits in order. There may be a variety of such orders, but the trick is to choose the traversal method that would best help you solve your particular issue.
Mention the application of DFS.
Locating the shortest path, systems for GPS navigation, locating a path, a connected component's nodes can identify, Websites for social networking, Crawlers for search engines, and P2P networks.
Which data structure is employed for a graph's BFS?
BFS, or Breadth-First Search, is a vertex-based method for locating the graph's shortest path. It makes use of a queue data structure with first in, first out ordering.
Conclusion
In this blog, we discussed moving the weighting scale alternatives under given constraints. We understood this problem with the help of an example. Then we discussed its algorithm. After that, we discussed its implementations in other languages like C++ and java. In the end, we saw the complexity analysis of the approach.