I was asked this problem in one of the interviews :
Given an undirected graph with N nodes and M edges. Each node is initially having some value A[i]. We are also given a number K.
Now in one operation we can take one of the edges and increment the value of the 2 nodes linked through that edge by K.
I have to find minimum no. of such operations to make value of all nodes in the graph equal or -1 if it is not possible.
Wasn't able to come up with any optimized approach. I was thinking to start with node having minimum value since in order to minimize the operations we should do as less operations as possible on maximum value node. But still not able to reach any correct approach.
Constraints : Not available . Please help if you have some other way to solve this problem.
Same question with slight variation
1537F - Figure Fixing
Wow seems interviewer got inspired with this hard problem :) Thanks a lot for sharing the problem.
I don't think the problem in your case is not as difficult as the problem above. as the value of k is fixed. You can uniquely determine how much to increase each node. You just have to make sure it is possible.. If it is possible ,Then the answer is simply half the sum of number of times each node have to be increased.
But in my case we also don't know the target value that we have to achieve for all nodes in graph
You can think of it like this.. first of all check if every node value % k is same or not, if it is not same, the answer is "NO", otherwise the target value for all node is the max node itself. After this the problem is same as mentioned above.
What if the graph is like a linked list with a node between two nodes having equal values.
Example
$$$3$$$ <-> $$$2$$$ <-> $$$3$$$ and k=1 How can we solve a case like this?
Select 3<->2 do +1 => 4<->3<->3 now select 3<->3 do +1 => 4<->4<->4
I was asking about how to predict the maximum values of a node for such a graph. According to tiasmondal the maximum value of a node after the operations have been performed would be equal to the value of maximum node before performing the operation. But that is not the case here.
It should be either the max value or the max value+k (you should see which option it is based on the fact that what you need to add in total should be dividable by 2k)
What if there's an edge between every 2 nodes, $$$n=4$$$, $$$k=1$$$ and the initial values are $$$0,4,5,5$$$? Then clearly you have to make all nodes equal to $$$7$$$(which is not "either the max value or the max value+k").
ok my bad. Seems like my idea is wrong :(
Just wondering why I am getting downvotes for discussing the solution for an interview problem :)