Given a sorted array, arr[] of size N representing the positions of the ith point on X-axis and an integer K, the task is to find the minimum distance required to travel to visit K point starting from the origin of X-axis.
Examples :
Input: arr[]={-30, -10, 10, 20, 50}, K = 3
Output: 40
Explanation:
Moving from origin to the second point. Therefore, the total distance traveled = 10.
Moving from the second point to the third point. Therefore, total traveled = 10 + 10 = 20
Moving from the third point to the fourth point. Therefore, total distance traveled = 20 + 20 = 40
Therefore, the total distance travelled to visit K point is 40.Input: arr[]={-1, -5, -4, -3, 6}, K = 3
Output: 6
Approach: The problem can be solved by visiting each K consecutive point and printing the minimum distance travelled to visit K consecutive points. Follow the steps below to solve the problem:
- Initialize a variable, say res, to store the minimum distance travelled to visit K point.
- Initialize a variable, say dist, to store the distance travelled to visit K points.
- Traverse the array and check the following conditions.
- If the value of (arr[i] >= 0 and arr[i + K -1] >= 0) is true then update dist = max(arr[i], arr[i + K -1]).
- Otherwise, dist = abs(arr[i]) + abs(arr[i + K – 1]) + min(abs(arr[i]), abs(arr[i + K – 1])).
- Finally, update res = min(res, dist).
- Finally, print the value of res.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum distance // travelled to visit K point int MinDistK(int arr[], int N, int K) { // Stores minimum distance travelled // to visit K point int res = INT_MAX; // Stores distance travelled // to visit points int dist = 0; // Traverse the array arr[] for (int i = 0; i <= (N - K); i++) { // If arr[i] and arr[i + K - 1] // are positive if (arr[i] >= 0 && arr[i + K - 1] >= 0) { // Update dist dist = max(arr[i], arr[i + K - 1]); } else { // Update dist dist = abs(arr[i]) + abs(arr[i + K - 1]) + min(abs(arr[i]), abs(arr[i + K - 1])); } // Update res res = min(res, dist); } return res; } // Driver Code int main() { int K = 3; // initial the array int arr[] = { -30, -10, 10, 20, 50 }; int N = sizeof(arr) / sizeof(arr[0]); cout<< MinDistK(arr, N, K); } |
Java
// Java program to implement // the above approach import java.util.*;class solution{ // Function to find the minimum // distance travelled to visit // K point static int MinDistK(int arr[], int N, int K) { // Stores minimum distance // travelled to visit K point int res = Integer.MAX_VALUE; // Stores distance travelled // to visit points int dist = 0; // Traverse the array arr[] for (int i = 0; i <= (N - K); i++) { // If arr[i] and arr[i + K - 1] // are positive if (arr[i] >= 0 && arr[i + K - 1] >= 0) { // Update dist dist = Math.max(arr[i], arr[i + K - 1]); } else { // Update dist dist = Math.abs(arr[i]) + Math.abs(arr[i + K - 1]) + Math.min(Math.abs(arr[i]), Math.abs(arr[i + K - 1])); } // Update res res = Math.min(res, dist); } return res; } // Driver Code public static void main(String args[]) { int K = 3; // initial the array int arr[] = {-30, -10, 10, 20, 50}; int N = arr.length; System.out.println(MinDistK(arr, N, K)); } } // This code is contributed by bgangwar59 |
Python3
# Python3 program to implement # the above approach import sys# Function to find the minimum distance # travelled to visit K point def MinDistK(arr, N, K): # Stores minimum distance travelled # to visit K point res = sys.maxsize # Stores distance travelled # to visit points dist = 0 # Traverse the array arr[] for i in range(N - K + 1): # If arr[i] and arr[i + K - 1] # are positive if (arr[i] >= 0 and arr[i + K - 1] >= 0): # Update dist dist = max(arr[i], arr[i + K - 1]) else: # Update dist dist = (abs(arr[i]) + abs(arr[i + K - 1]) + min(abs(arr[i]), abs(arr[i + K - 1]))) # Update res res = min(res, dist) return res # Driver Code if __name__ == '__main__': K = 3 # Initial the array arr = [ -30, -10, 10, 20, 50 ] N = len(arr) print(MinDistK(arr, N, K)) # This code is contributed by ipg2016107 |
C#
// C# program to implement// the above approach using System;class GFG{ // Function to find the minimum // distance travelled to visit // K point static int MinDistK(int[] arr, int N, int K) { // Stores minimum distance // travelled to visit K point int res = Int32.MaxValue; // Stores distance travelled // to visit points int dist = 0; // Traverse the array arr[] for(int i = 0; i <= (N - K); i++) { // If arr[i] and arr[i + K - 1] // are positive if (arr[i] >= 0 && arr[i + K - 1] >= 0) { // Update dist dist = Math.Max(arr[i], arr[i + K - 1]); } else { // Update dist dist = Math.Abs(arr[i]) + Math.Abs(arr[i + K - 1]) + Math.Min(Math.Abs(arr[i]), Math.Abs(arr[i + K - 1])); } // Update res res = Math.Min(res, dist); } return res; } // Driver Code public static void Main() { int K = 3; // Initial the array int[] arr = { -30, -10, 10, 20, 50}; int N = arr.Length; Console.WriteLine(MinDistK(arr, N, K)); } }// This code is contributed by code_hunt |
Javascript
<script>// JavaScript program to implement// the above approach// Function to find the minimum// distance travelled to visit// K pointfunction MinDistK(arr, N, K){ // Stores minimum distance // travelled to visit K point let res = Number.MAX_VALUE; // Stores distance travelled // to visit points let dist = 0; // Traverse the array arr[] for (let i = 0; i <= (N - K); i++) { // If arr[i] and arr[i + K - 1] // are positive if (arr[i] >= 0 && arr[i + K - 1] >= 0) { // Update dist dist = Math.max(arr[i], arr[i + K - 1]); } else { // Update dist dist = Math.abs(arr[i]) + Math.abs(arr[i + K - 1]) + Math.min(Math.abs(arr[i]), Math.abs(arr[i + K - 1])); } // Update res res = Math.min(res, dist); } return res;}// Driver Code let K = 3; // initial the array let arr = [-30, -10, 10, 20, 50]; let N = arr.length; document.write(MinDistK(arr, N, K)); </script> |
Output
40
Time Complexity: O(N-K), Where n is the length of the given array for the given K value.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
