Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Sample Example
3.
Algorithm 
4.
Implementation in C++
5.
Implementation in Java
6.
Implementation in Python
6.1.
Complexity analysis
7.
Frequently Asked Questions
7.1.
What Is Graph Traversal?
7.2.
Mention the application of DFS.
7.3.
Which data structure is employed for a graph's BFS?
8.
Conclusion
Last Updated: Mar 27, 2024

Move weighting scale alternate under given constraints

Author Shivani Singh
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

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.

Sample Example of approach
Sample Example of approach
Sample Example of approach
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 of the approach

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;
}

Output

The sequence is: 
7 11 7 

Implementation in Java

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);
    }
}

Output

The sequence is: 
7 11 7 

Implementation in Python

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)

Output

The sequence is: 
7 11 7 

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.  

For more content, Refer to our guided paths on Coding Ninjas Studio to upskill yourself.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Thankyou
Previous article
Check If Removing a Given Edge Disconnects a Graph
Next article
Count the minimum number of edges between two vertices of a Graph
Live masterclass