Minimum distance to visit given K points on X-axis after starting from the origin

0 0 5 minutes read

Given a sorted array, arr[] of size N representing the positions of the i^th 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 point
function 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

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 zambiatek!