N objects are placed on X-axis, and coordinates are given. Starting your journey with coordinate 0, find minimum distance you need to travel to collect K objects (If multiple objects are placed on same position, you may collect some or all of them).
Examples:
Input: arr[] = {10, -10, -30, 20, 50}, K = 3 Output: 40 Explanation: Start with 0 (initial position) journey will be 0 --> (-10) --> 10 --> 20 . Sum of distance is |-10-0| + |10-(-10)| + |20-10| = 40, which is minimum possible. Input: arr[] = {4, -3, 5}, K = 2 Output: 5 Explanation: Start with 0 (initial position) journey will be 0 --> 4 --> 5 . Sum of distance is |4-0|+ |5-4| = 5, which is minimum possible.
Approach:
Here are some observations and steps to solve given problem
Observations:-
- If two objects with coordinates at x1 and x2 are collected, both from positive side (or both from negative side) then total distance will be max(|x1|, |x2|), if current position is 0.
- Switching direction (from negative to positive Or vice versa) more than 1 time, will add some additional distance to answer.
Solution:-
- Sort all the points in increasing order of coordinates.
- Select all subarrays of length K, and for each subarray optimal total distance will be as :-
- If all the coordinates are negative, leftmost coordinate denotes total distance.
- If all the coordinates are positive, rightmost coordinate denotes total distance.
- If subarray contains both negative and positive, then there are 2 ways – select all negative first and then switch to positive Or vice versa.
- Minimum distance among all these subarrays, is our optimal answer.
Below is the implementation of above approach:
#include <bits/stdc++.h> using namespace std; int minDistance(int arr[], int N, int K) { if (N < K) return -1; // sort the coordinates sort(arr, arr + N); int ans = 1e9; // select subarray of length K, starting at index i for (int i = 0; i < N - K + 1; i++) { int left = arr[i]; int right = arr[i + K - 1]; if (right <= 0) { // both ends are negative side left = abs(left); ans = min(ans, left); } else if (left >= 0) { // both ends are positive side ans = min(ans, right); } else { left = abs(left); // first left and then right ans = min(ans, left + left + right); // first right and then left ans = min(ans, right + right + left); } } return ans; } // Driver code int main() { int N = 5; int arr[] = { 10, -10, -30, 20, 50 }; int K = 3; cout << minDistance(arr, N, K); return 0; }
Output:
40
Time Complexity: O(N logN)
Space Complexity: O(N)
Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.