Minimum length of wire needed to connect all points who have value as 0 with at least one point with value 1.
Given two arrays Point[] and Value[] of length N, where Point[] represents the position of N points on a horizontal line. Then your task is to output the minimum length of line needed to connect all points having Value[i] = 0 with at least one point having Value[i] = 1, directly or indirectly.
Note: There will be at least one point with value = 1.
Examples:
Input: N = 6, Point[] = {1, 5, 6, 7, 11, 14}, Value[] = {1, 0, 0, 0, 1, 0}
Output: 9
Explanation:The points 1, 5, 6, 7, 11 and 14 are situated on a horizontal line having values 1, 0, 0, 0, 1, and 0 respectively. The connection of points took place as:
- First Connection: Join 14 with 11 with 3-unit length of line.
- Second Connection: Join 5 with 1 with 4-unit length of line. Till total line needed to connect is 3 + 4 = 7.
- Third Connection: Join 6 with 5, So that 6 will indirectly connect with 1 having value as 1. Required line needed to connect 5 and 6 is 1. Total length of line till now is 7 + 1 = 8.
- Fourth Connection: Join 7 with 6, So that 7 will indirectly connect with 1 having value as 1. Required line needed to connect 7 and 6 is 1. Total length of line till now is 8 + 1 = 9.
It can be verified that, It is not possible to connect all the points having value as 0 with at least 1 point having value as 1 directly or indirectly in less than 9 unit length line. Therefore, output is 9.
Input: N = 5, Point[] = {5, 12, 15, 19, 32}, Value = {1, 0, 0, 1, 0}
Output: 20
Explanation: It can be verified that the minimum length of wire will be 20. If villages having Values 0 are connected optimally with Villages having Values as 1.
Approach:
The problem is based on the Greedy logic and can be solved using Sliding Window technique. By modifying the Sliding Window algorithm with a slight variation according to the problem statement, we can solve this problem. The Sliding Window approach is used to efficiently traverse the points. The window slides over the points, and for each window, it checks if the point has value equal to 1 or 0. If a point have value equal to 0, it calculates the maximum distance between two points and the total distance of all points in the window. The total distance minus the maximum distance is added to Ans, which represents the minimum unit length of line needed to connect all points having value 0 with at least one point having value 1 directly or indirectly.
Steps were taken to solve the problem:
- Declare two variables let say i and Ans as end point of Sliding Window and to store min length of wire.
- Run a While loop with condition (i < N) and follow below mentioned steps under the scope of loop:
- If Point[i] == 1, then continue
- Else keep incrementing i till Point[i] = 0
- Now, we have a contiguous segment of 0s which needs to be connected to 1s
- Find the maximum distance between the points in the contiguous segment.
- Now, if the contiguous segment is surrounded by 1 on both sides, then we can add all the distances between the points except the maximum distance to Ans. This is because we will connect all the points that lie to the left of the maximum distance to the left 1 and all the points that lie to the right of maximum distance to the right 1.
- Else, if the contiguous segment has 1 on a single side, then we need to add all the distances to Ans.
- Output the value of Ans variable.
Code to implement the approach:
C++
#include <iostream> #include <vector> #include <climits> using namespace std; // Function to print minimum length of line needed to connect void Min_Length( int N, vector< int >& Value, vector< int >& Point) { // Ending point of Sliding Window int i = 0; // Variable to store Min_length of line needed long long ans = 0; // While Loop for traversing Sliding Window while (i < N) { // Find the end of the current group of points with the same value int j = i; while (j + 1 < N && Value[j] == Value[j + 1]) { j++; } // If the current group of points has a value equal to 1, move to the next group if (Value[i] == 1) { i = j + 1; continue ; } // Variables to store maximum distance between two points // and the total distance of all points in the current group int maxDist = 0; // Rename 'max' to 'maxDist' long long sum = 0; for ( int k = i - 1; k <= j; k++) { if (k >= 0 && k < N) { if (k + 1 < N) { sum += Point[k + 1] - Point[k]; maxDist = max(maxDist, Point[k + 1] - Point[k]); } } } // If the current group is at either end of the line of points, // add the total distance to Ans if (i - 1 == -1 || j + 1 == N) ans += sum; else // If not at either end, subtract the maximum distance from // the total distance and add to ans ans += sum - maxDist; // Move to the next group of points i = j + 1; } // Printing the minimum unit length of line needed cout << ans << endl; } // Driver function int main() { // Inputs int N = 8; vector< int > Value = {1, 0, 1, 0, 0, 1, 1, 0}; vector< int > Point = {1, 5, 6, 7, 11, 14, 16, 18}; // Function call Min_Length(N, Value, Point); return 0; } |
Java
// Java code to implement the approach import java.util.*; // Driver Class class Main { // Driver Function public static void main(String[] args) throws java.lang.Exception { // Inputs int N = 8 ; int [] Value = { 1 , 0 , 1 , 0 , 0 , 1 , 1 , 0 }; int Point[] = { 1 , 5 , 6 , 7 , 11 , 14 , 16 , 18 }; // Function_call Min_Length(N, Value, Point); } // Method to print // minimum length of line needed to connect public static void Min_Length( int N, int [] Value, int [] Point) { // Ending point of // Sliding Window int i = 0 ; // Variable to store // Min_length of line needed long ans = 0 ; // While Loop for traversing // Sliding Window while (i < N) { // Find the end of the current group of points // with same value int j = i; while (j + 1 < N && Value[j] == Value[j + 1 ]) { j++; } // If current group of points has value equal to // 1, move to next group if (Value[i] == 1 ) { i = j + 1 ; continue ; } // Variables to store maximum distance between // two points and total distance of all points // in current group int max = 0 ; long sum = 0 ; for ( int k = i - 1 ; k <= j; k++) { if (k >= 0 && k < N) { if (k + 1 < N) { sum += Point[k + 1 ] - Point[k]; max = Math.max(max, Point[k + 1 ] - Point[k]); } } } // If current group is at either end of the line // of points, add total distance to Ans if (i - 1 == - 1 || j + 1 == N) ans += sum; else // If not at either end, subtract maximum // distance from total distance and add to // ans ans += sum - max; // Move to next group of points i = j + 1 ; } // Printing the minimum // unit length of line needed System.out.println(ans); } } |
Python3
def min_length(N, Value, Point): # Ending point of Sliding Window i = 0 # Variable to store Min_length of line needed ans = 0 # While Loop for traversing Sliding Window while i < N: # Find the end of the current group of points with the same value j = i while j + 1 < N and Value[j] = = Value[j + 1 ]: j + = 1 # If the current group of points has a value equal to 1, move to the next group if Value[i] = = 1 : i = j + 1 continue # Variables to store maximum distance between two points # and the total distance of all points in the current group max_dist = 0 total_distance = 0 for k in range (i - 1 , j + 1 ): if 0 < = k < N: if k + 1 < N: total_distance + = Point[k + 1 ] - Point[k] max_dist = max (max_dist, Point[k + 1 ] - Point[k]) # If the current group is at either end of the line of points, # add the total distance to Ans if i - 1 = = - 1 or j + 1 = = N: ans + = total_distance else : # If not at either end, subtract the maximum distance from # the total distance and add to ans ans + = total_distance - max_dist # Move to the next group of points i = j + 1 # Printing the minimum unit length of line needed print (ans) # Driver function if __name__ = = "__main__" : # Inputs N = 8 Value = [ 1 , 0 , 1 , 0 , 0 , 1 , 1 , 0 ] Point = [ 1 , 5 , 6 , 7 , 11 , 14 , 16 , 18 ] # Function call min_length(N, Value, Point) |
C#
using System; using System.Collections.Generic; public class Program { // Function to print minimum length of line needed to connect public static void Min_Length( int N, List< int > Value, List< int > Point) { // Ending point of Sliding Window int i = 0; // Variable to store Min_length of line needed long ans = 0; // While Loop for traversing Sliding Window while (i < N) { // Find the end of the current group of points with the same value int j = i; while (j + 1 < N && Value[j] == Value[j + 1]) { j++; } // If the current group of points has a value equal to 1, move to the next group if (Value[i] == 1) { i = j + 1; continue ; } // Variables to store maximum distance between two points // and the total distance of all points in the current group int maxDist = 0; long sum = 0; for ( int k = i - 1; k <= j; k++) { if (k >= 0 && k < N) { if (k + 1 < N) { sum += Point[k + 1] - Point[k]; maxDist = Math.Max(maxDist, Point[k + 1] - Point[k]); } } } // If the current group is at either end of the line of points, // add the total distance to Ans if (i - 1 == -1 || j + 1 == N) ans += sum; else // If not at either end, subtract the maximum distance from // the total distance and add to ans ans += sum - maxDist; // Move to the next group of points i = j + 1; } // Printing the minimum unit length of line needed Console.WriteLine(ans); } // Driver function public static void Main() { // Inputs int N = 8; List< int > Value = new List< int > { 1, 0, 1, 0, 0, 1, 1, 0 }; List< int > Point = new List< int > { 1, 5, 6, 7, 11, 14, 16, 18 }; // Function call Min_Length(N, Value, Point); } } // This code is contributed by shivamgupta310570 |
Javascript
// Function to print minimum length of line needed to connect function Min_Length(N, Value, Point) { // Ending point of Sliding Window let i = 0; // Variable to store Min_length of line needed let ans = 0; // While Loop for traversing Sliding Window while (i < N) { // Find the end of the current group of points with the same value let j = i; while (j + 1 < N && Value[j] === Value[j + 1]) { j++; } // If the current group of points has a value equal to 1, move to the next group if (Value[i] === 1) { i = j + 1; continue ; } // Variables to store maximum distance between two points // and the total distance of all points in the current group let maxDist = 0; // Rename 'max' to 'maxDist' let sum = 0; for (let k = i - 1; k <= j; k++) { if (k >= 0 && k < N) { if (k + 1 < N) { sum += Point[k + 1] - Point[k]; maxDist = Math.max(maxDist, Point[k + 1] - Point[k]); } } } // If the current group is at either end of the line of points, // add the total distance to Ans if (i - 1 === -1 || j + 1 === N) ans += sum; else // If not at either end, subtract the maximum distance from // the total distance and add to ans ans += sum - maxDist; // Move to the next group of points i = j + 1; } // Printing the minimum unit length of line needed console.log(ans); } // Driver function function main() { // Inputs const N = 8; const Value = [1, 0, 1, 0, 0, 1, 1, 0]; const Point = [1, 5, 6, 7, 11, 14, 16, 18]; // Function call Min_Length(N, Value, Point); } // Call the main function main(); |
7
Time Complexity: O(N)
Auxiliary Space: O(1), where N is the Number of points.
Contact Us