Given N number of integers in sorted format, where each integer Ai for all(1 ? i ? N), denotes the join of two points (0, Ai) and (Ai, 0) and forms a line by joining these two points, also given Q number of coordinates in form of (X, Y) in the first Quadrant. Return the minimum number of lines needed to cross to reach the origin from (X, Y) in each query. if (X, Y) lies on any of the lines, return -1 as output.
Examples:
Input: N = 2, Points[] = {1, 2}, Q = 1, X = 3, Y = 2
Output: 2
Explanation:
Explanation of Input case 1
There is only one query, In which the point is (2, 3), It can be verified that for reaching origin given point need to cross 2 lines.
Input: N = 3, Points[] = {1, 2, 5}, Q = 3
X = 0, Y = 0
X = 1, Y = 1
X = 4, Y = 3
Output:
0
-1
3
Explanation:Explanation of Input case 2
- Query 1:
- (X, Y) are (0, 0), Point is already present at origin, Therefore, no need to cross any line, Output is 0.
- Query 2:
- Given point is (1, 1), Which is present at line joining points (0, 2) and (2, 0). Hence the output is -1, because point is on line.
- Query 3:
- Given point is (3, 4), It can be verified that for reaching origin, We need to cross 3 lines.Hence the output is 3.
Approach: Implement the idea below to solve the problem
The problem is observation based and can be solved by using TreeSet and HashMap. For more clarification of problem see the Concept of approach section below. Using data structure like TreeSet and Map reduces complexity very much.
Concept of approach:
The problem is observation based. There are some points, Which are needed to follow to solve the problem:
- Condition when point lies on any line:
- It should be noted that only those co-ordinates (X, Y) will lie on a line, Whom sum of X and Y co-ordinate is equal to starting of ending point of line. For checking this condition, We will check if HashMap contains (X+Y) or not. If contains then print -1 as output.
- When point doesn’t lie on any line:
- In such condition, Get a floor value of (X+Y) from TreeSet, Formally set.floor(X, Y) and store it in a variable let say floor, If floor is null then print zero else get index of floor, Formally map.get(Floor) from HashMap and store it in the variable let say Index.and print (index+1) as output.
Steps were taken to solve the problem:
- Create TreeSet<Integer> and HashMap<long, Integer> to store values present in Points[].
- Initialize TreeSet with elements of Points[] and HashMap with elements of points along with their index.
- Run a loop for 1 to Q times and follow the below-mentioned steps under the scope of the loop:
- Create a Sum variable and initialize it with (X+Y).
- If HashMap contains Sum, then print -1 as output.
- else get set.floor(Sum) from TreeSet, Then get its index from the map and print it as output.
- Create a Sum variable and initialize it with (X+Y).
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find lines crossed by the pointvoid minimumLines(int N, int points[], int Q, int X_coordinate[], int Y_coordinate[]){ // TreeSet for storing points set<int> set; // HashMap for storing points and their index unordered_map<int, int> hash; // Loop for initializing TreeSet and HashMap for (int i = 0; i < N; i++) { int val = points[i]; set.insert(val); hash[val] = i; } // Loop for number of times Query asked for (int i = 0; i < Q; i++) { // X coordinate int x = X_coordinate[i]; // Y coordinate int y = Y_coordinate[i]; // Sum of both coordinates long sum = x + y; // Variable to store minimum number of // lines int ans = 0; // Checking if sum exists in HashMap or not if (hash[sum]) { // Printing -1 as output. ans = -1; cout << (ans) << endl; continue; } // Checking floor value of sum auto floor = --set.upper_bound(sum); // Printing number of lines needed // to cross by getting floor value // of sum if (floor != set.end()) { int ind = hash[*floor]; ans = ind + 1; } cout << ans << endl; }}// Driver Codeint main(){ int N = 3; int points[] = { 1, 2, 5 }; int Q = 3; // X and Y coordinates of Q queries // formally Q number of (X, Y) points int X_coordinate[] = { 0, 1, 3 }; int Y_coordinate[] = { 0, 1, 4 }; // Function call minimumLines(N, points, Q, X_coordinate, Y_coordinate);}// This code is contributed by Pushpesh Raj. |
Java
// Java code to implement the approachimport java.io.*;import java.lang.*;import java.util.*;public class GFG { // Driver Code public static void main(String[] args) throws java.lang.Exception { int N = 3; int[] points = { 1, 2, 5 }; int Q = 3; // X and Y coordinates of Q queries // formally Q number of (X, Y) points int[] X_coordinate = { 0, 1, 3 }; int[] Y_coordinate = { 0, 1, 4 }; // Function call minimumLines(N, points, Q, X_coordinate, Y_coordinate); } // Function to find lines crossed by the point public static void minimumLines(int N, int points[], int Q, int X_coordinate[], int Y_coordinate[]) { // TreeSet for storing points TreeSet<Long> set = new TreeSet<>(); // HashMap for storing points and their index Map<Long, Integer> hash = new HashMap<>(); // Loop for initializing TreeSet and HashMap for (int i = 0; i < N; i++) { long val = points[i]; set.add(val); hash.put(val, i); } // Loop for number of times Query asked for (int i = 0; i < Q; i++) { // X coordinate int x = X_coordinate[i]; // Y coordinate int y = Y_coordinate[i]; // Sum of both coordinates long sum = x + y; // Variable to store minimum number of // lines int ans = 0; // Checking if sum exists in HashMap or not if (hash.containsKey(sum)) { // Printing -1 as output. ans = -1; System.out.println(ans); continue; } // Checking floor value of sum Long floor = set.floor(sum); // Printing number of lines needed // to cross by getting floor value // of sum if (floor != null) { int ind = hash.get(floor); ans = ind + 1; } System.out.println(ans); } }} |
Python3
# Python code to implement the approachimport bisect# Driver Codedef main(): N = 3 points = [1, 2, 5] Q = 3 # X and Y coordinates of Q queries # formally Q number of (X, Y) points X_coordinate = [0, 1, 3] Y_coordinate = [0, 1, 4] # Function call minimumLines(N, points, Q, X_coordinate, Y_coordinate)# Function to find lines crossed by the pointdef minimumLines(N, points, Q, X_coordinate, Y_coordinate): # Set for storing points Set = set() # Dictionary for storing points and their index hash = {} # Loop for initializing Set and Dictionary for i in range(N): val = points[i] Set.add(val) hash[val] = i # Loop for number of times Query asked for i in range(Q): # X coordinate x = X_coordinate[i] # Y coordinat y = Y_coordinate[i] # Sum of both coordinates Sum = x + y # Variable to store minimum number of # lines ans = 0 # Checking if Sum exists in HashMap or not if (Sum in hash): # Printing -1 as output. ans = -1 print(ans) continue # Checking floor value of Sum floor, val = lowerBound(Set, Sum) # Printing number of lines needed # to cross by getting floor value # of Sum if (floor >= 0): ind = hash.get(val) ans = ind + 1 print(ans)def lowerBound(Set, Sum): lb = -1 Set = list(Set) Set.sort() for val in Set: if val < Sum: lb += 1 else: break return lb, Set[lb] if lb >= 0 else -1if __name__ == "__main__": main()# This code is contributed by shubhamsingh |
Javascript
// Javascript code to implement the approach// Function to find lines crossed by the pointfunction minimumLines(N, points, Q, X_coordinate, Y_coordinate){ // TreeSet for storing points let set = new Set(); // HashMap for storing points and their index hash = {}; // Loop for initializing TreeSet and HashMap for(let i = 0; i < N; i++) { let val = points[i]; set.add(val); hash[val] = i; } // Loop for number of times Query asked for (let i = 0; i < Q; i++) { // X coordinate x = X_coordinate[i]; // Y coordinate y = Y_coordinate[i]; // Sum of both coordinates sum = x + y; // Variable to store minimum number of // lines ans = 0; // Checking if sum exists in HashMap or not if (hash[sum]) { // Printing -1 as output. ans = -1; console.log(ans); continue; } // Checking floor value of sum let [floor, val] = lowerBound(set, sum) // Printing number of lines needed // to cross by getting floor value // of sum if (floor >= 0){ ind = hash[val] ans = ind + 1 } console.log(ans); }}function lowerBound(Set, Sum){ lb = -1 Set = [...Set].sort() for (let val in Set){ if (val < Sum){ lb += 1 } else{ break } } return [lb, lb >=0 ? Set[lb] : -1]}// Driver CodeN = 3;points = [ 1, 2, 5 ];Q = 3;// X and Y coordinates of Q queries// formally Q number of (X, Y) pointsX_coordinate = [ 0, 1, 3 ];Y_coordinate = [ 0, 1, 4 ];// Function callminimumLines(N, points, Q, X_coordinate,Y_coordinate);// This code is contributed by Shubham SIngh. |
C#
using System;using System.Collections.Generic;class GFG { static void Main(string[] args) { int N = 3; int[] points = { 1, 2, 5 }; int Q = 3; // X and Y coordinates of Q queries // formally Q number of (X, Y) points int[] X_coordinate = { 0, 1, 3 }; int[] Y_coordinate = { 0, 1, 4 }; // Function call minimumLines(N, points, Q, X_coordinate, Y_coordinate); } // Function to find lines crossed by the point static void minimumLines(int N, int[] points, int Q, int[] X_coordinate, int[] Y_coordinate) { // TreeSet for storing points SortedSet<long> set = new SortedSet<long>(); // HashMap for storing points and their index Dictionary<long, int> hash = new Dictionary<long, int>(); // Loop for initializing TreeSet and HashMap for (int i = 0; i < N; i++) { long val = points[i]; set.Add(val); hash.Add(val, i); } // Loop for number of times Query asked for (int i = 0; i < Q; i++) { // X coordinate int x = X_coordinate[i]; // Y coordinate int y = Y_coordinate[i]; // Sum of both coordinates long sum = x + y; // Variable to store minimum number of // lines int ans = 0; // Checking if sum exists in HashMap or not if (hash.ContainsKey(sum)) { // Printing -1 as output. ans = -1; Console.WriteLine(ans); continue; } // Checking floor value of sum long floor = set.GetViewBetween(long.MinValue, sum) .Max; // Printing number of lines needed // to cross by getting floor value // of sum if (floor != 0) { int ind = hash[floor]; ans = ind + 1; } Console.WriteLine(ans); } }} |
Output
0 -1 3
Time Complexity: O(log(N))
Auxiliary Space: O(N)
Another Approach: using Binary Search
- First, we need to create a TreeSet and HashMap in order to store the points.
- Traverse through each point and insert it into the TreeSet and HashMap respectively. In the HashMap, store each point along with its index.
- Run a loop for Q number of times, where Q is the number of queries.
- For each query, get the X and Y coordinates.
- Calculate the sum of X and Y coordinates.
- If the HashMap contains the sum, return -1 as the output.
- Else, get the floor value of the sum from the TreeSet.
- If the floor value is not null, get its index from the HashMap.
- Return the index + 1 as the minimum number of lines to cross to reach the origin.
- Repeat the above steps for all queries.
- Finally, output the minimum number of lines for each query.
Implementation takes input as follows:
- N: The number of integers in the sorted format.
- points[]: An array containing N integers.
- Q: The number of queries to be performed.
- X_coordinate[]: An array containing X-coordinates for each query.
- Y_coordinate[]: An array containing Y-coordinates for each query.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std; // Function to find lines crossed by the pointvoid minimumLines(int N, int points[], int Q, int X_coordinate[], int Y_coordinate[]){ // TreeSet for storing points set<int> set; // HashMap for storing points and their index unordered_map<int, int> hash; // Loop for initializing TreeSet and HashMap for (int i = 0; i < N; i++) { int val = points[i]; set.insert(val); hash[val] = i; } // Loop for number of times Query asked for (int i = 0; i < Q; i++) { // X coordinate int x = X_coordinate[i]; // Y coordinate int y = Y_coordinate[i]; // Sum of both coordinates long sum = x + y; // Variable to store minimum number of // lines int ans = 0; // Checking if sum exists in HashMap or not if (hash[sum]) { // Printing -1 as output. ans = -1; cout << (ans) << endl; continue; } // Checking floor value of sum auto floor = --set.upper_bound(sum); // Printing number of lines needed // to cross by getting floor value // of sum if (floor != set.end()) { int ind = hash[*floor]; ans = ind + 1; } cout << ans << endl; }} // Driver Codeint main(){ int N = 3; int points[] = { 1, 2, 5 }; int Q = 3; // X and Y coordinates of Q queries // formally Q number of (X, Y) points int X_coordinate[] = { 0, 1, 3 }; int Y_coordinate[] = { 0, 1, 4 }; minimumLines(N, points, Q, X_coordinate, Y_coordinate); return 0;} |
Java
// Java code for above approachimport java.util.*;class Main {// Function to find lines crossed by the pointstatic void minimumLines(int N, int points[], int Q,int X_coordinate[], int Y_coordinate[]){ // TreeSet for storing points NavigableSet<Integer> set = new TreeSet<>(); // HashMap for storing points and their index HashMap<Integer, Integer> hash = new HashMap<>(); // Loop for initializing TreeSet and HashMap for (int i = 0; i < N; i++) { int val = points[i]; set.add(val); hash.put(val, i); } // Loop for number of times Query asked for (int i = 0; i < Q; i++) { // X coordinate int x = X_coordinate[i]; // Y coordinate int y = Y_coordinate[i]; // Sum of both coordinates long sum = x + y; // Variable to store minimum number of // lines int ans = 0; // Checking if sum exists in HashMap or not if (hash.containsKey((int)sum)) { // Printing -1 as output. ans = -1; System.out.println(ans); continue; } // Checking floor value of sum Integer floor = set.floor((int)sum); // Printing number of lines needed // to cross by getting floor value // of sum if (floor != null) { int ind = hash.get(floor); ans = ind + 1; } System.out.println(ans); }}// Driver Codepublic static void main(String[] args){ int N = 3; int points[] = { 1, 2, 5 }; int Q = 3; // X and Y coordinates of Q queries // formally Q number of (X, Y) points int X_coordinate[] = { 0, 1, 3 }; int Y_coordinate[] = { 0, 1, 4 }; minimumLines(N, points, Q, X_coordinate, Y_coordinate);}}// This code is contributed Utkarsh Kumar. |
Python
def minimumLines(N, points, Q, X_coordinate, Y_coordinate): # Set for storing points set1 = set() # Hashmap for storing points and their index hash1 = {} # Loop for initializing Set and hashmap for i in range(N): val = points[i] set1.add(val) hash1[val] = i # Loop for number of times Query asked for i in range(Q): # X coordinate x = X_coordinate[i] # Y coordinate y = Y_coordinate[i] # Sum of both coordinates sum1 = x + y # Variable to store minimum number of lines ans = 0 # Checking if sum exists in hashmap or not if sum1 in hash1: # Printing -1 as output. ans = -1 print(ans) continue # Checking floor value of sum floor_list = [e for e in set1 if e < sum1] floor = floor_list[-1] if floor_list else None # Printing number of lines needed # to cross by getting floor value # of sum if floor != None: ind = hash1[floor] ans = ind + 1 print(ans)# Driver CodeN = 3points = [ 1, 2, 5 ]Q = 3# X and Y coordinates of Q queries# formally Q number of (X, Y) pointsX_coordinate = [ 0, 1, 3 ]Y_coordinate = [ 0, 1, 4 ]minimumLines(N, points, Q, X_coordinate, Y_coordinate) |
C#
using System;using System.Collections.Generic;class Program { // Function to find lines crossed by the point static void MinimumLines(int N, int[] points, int Q, int[] X_coordinate, int[] Y_coordinate) { // TreeSet for storing points SortedSet<int> set = new SortedSet<int>(); // Dictionary for storing points and their index Dictionary<int, int> hash = new Dictionary<int, int>(); // Loop for initializing TreeSet and HashMap for (int i = 0; i < N; i++) { int val = points[i]; set.Add(val); hash[val] = i; } // Loop for number of times Query asked for (int i = 0; i < Q; i++) { // X coordinate int x = X_coordinate[i]; // Y coordinate int y = Y_coordinate[i]; // Sum of both coordinates long sum = x + y; // Variable to store minimum number of // lines int ans = 0; // Checking if sum exists in Dictionary or not if (hash.ContainsKey((int)sum)) { // Printing -1 as output. ans = -1; Console.WriteLine(ans+" "); continue; } // Checking floor value of sum var floor = set.GetViewBetween(int.MinValue, (int)(sum - 1)).Max; // Printing number of lines needed // to cross by getting floor value // of sum if (floor != int.MaxValue && hash.ContainsKey(floor)) { int ind = hash[floor]; ans = ind + 1; } Console.WriteLine(ans+" "); } } // Driver Code static void Main(string[] args) { int N = 3; int[] points = { 1, 2, 5 }; int Q = 3; // X and Y coordinates of Q queries // formally Q number of (X, Y) points int[] X_coordinate = { 0, 1, 3 }; int[] Y_coordinate = { 0, 1, 4 }; MinimumLines(N, points, Q, X_coordinate, Y_coordinate); }} |
Javascript
function minimumLines(N, points, Q, X_coordinate, Y_coordinate) { // Set for storing points let set = new Set(); // Map for storing points and their index let hash = new Map(); // Loop for initializing Set and Map for (let i = 0; i < N; i++) { let val = points[i]; set.add(val); hash.set(val, i); } // Loop for number of times Query asked for (let i = 0; i < Q; i++) { // X coordinate let x = X_coordinate[i]; // Y coordinate let y = Y_coordinate[i]; // Sum of both coordinates let sum = x + y; // Variable to store minimum number of lines let ans = 0; // Checking if sum exists in Map or not if (hash.has(sum)) { // Printing -1 as output. ans = -1; console.log(ans); continue; } // Checking floor value of sum let floor = Array.from(set).filter(e => e < sum).pop(); // Printing number of lines needed // to cross by getting floor value // of sum if (floor !== undefined) { let ind = hash.get(floor); ans = ind + 1; } console.log(ans); }}// Driver Codelet N = 3;let points = [ 1, 2, 5 ];let Q = 3;// X and Y coordinates of Q queries// formally Q number of (X, Y) pointslet X_coordinate = [ 0, 1, 3 ];let Y_coordinate = [ 0, 1, 4 ];minimumLines(N, points, Q, X_coordinate, Y_coordinate); |
Output
0 -1 3
Time Complexity: O(Q * log N)
Auxiliary Space: O(N)
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!
Share your thoughts in the comments
