#include<bits/stdc++.h>
string read(int n, vector<int> book, int target)
{
map<int,int> m;
for(int i=0;i<book.size();i++){
int rem=target - book[i];
if(m.find(rem)!=m.end()){
return "YES";
}
m[book[i]]=i;
}
return "NO";
}
Problem
Submissions
Hints & solutions
Discuss
Two Sum
Easy
0/40
Average time to solve is 15m
Contributed by
170 upvotes
Asked in company
Problem statement
Sam want to read exactly ‘TARGET’ number of pages.
He has an array ‘BOOK’ containing the number of pages for ‘N’ books.
Return YES/NO, if it is possible for him to read any 2 books and he can meet his ‘TARGET’ number of pages.
Example:Input: ‘N’ = 5, ‘TARGET’ = 5
‘BOOK’ = [4, 1, 2, 3, 1]
Output: YES
Explanation:
Sam can buy 4 pages book and 1 page book.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of the input contains two integers, ‘N’ and ‘TARGET’, representing the number of books and target pages.
The next line of each test case contains ‘N’ space-separated integers representing the number of pages.
Return a string YES/NO, if it is possible for sam to read any 2 books and he can meet his ‘TARGET’ number of pages.
Sample Input 1:
5 5
4 1 2 3 1
Sample Output 1 :
YES
Explanation Of Sample Input 1:
Sam can buy 4 pages book and 1-page book.
Sample Input 2:
2 1
1 2
Sample Output 2 :
NO
Expected Time Complexity:
O( N ), Where N is the length of the array.
Constraints:
1 <= N <= 10^3
1 <= BOOK[i], TARGET <= 10^6
Time Limit: 1 sec
Hint
Hint 1
Mapping of books ?
Approaches (1)
Approach 1
Hashing
Approach:
The solution to the problem lies in using a hash-map to check if there is any book with (TARGET-number of pages in current book) pages already present. This can be done by traversing the whole array once.
The steps are as follows:
Function string read(int N, [int] BOOK, int TARGET)
- Create a hash map ‘mp’, mapping integer to boolean.
- For loop ‘itr’ in range 0 to N-1.
- If (TARGET - BOOK[itr]) is present in mp.
- Return “YES”.
- Set mp at BOOK[itr] as true.
- If (TARGET - BOOK[itr]) is present in mp.
- Return “NO”
Time Complexity
O( N ), Where N is the length of the array.
Hashing takes constant time and we are traversing the array of size N once.
Hence the time complexity is O( N ).
Space Complexity
O( N ), Where N is the length of the array.
As we are maintaining a hash map, which can take N elements of the array for the worst case.
Hence the space complexity is O( N ).
Code Solution
(100% EXP penalty)
Two Sum
All tags
Sort by
Interview problems
other method
can we first convert given array to map and then solve the question further?
4 views
0 replies
1 upvote
Interview problems
Two Sum in Java using Hashmap
public class Solution {
public static String read(int n, int []book, int target){
HashMap<Integer,Integer> hmap=new HashMap<>();
for(int i=0;i<n;i++){
int b1=book[i];
int b2=target-b1;
if(hmap.containsKey(b2)){
return "YES";
}
hmap.put(b1, i);
}
return "NO";
}
}
28 views
0 replies
0 upvotes
Interview problems
Best CPP approach || 2-pointers
Time Complexity: O(n)
Space Complexity: O(1)
Approach: Instead of using hash set, we can take advantage of not returning the array indices and sort it to make things easier for us to use 2 pointers.
string read(int n, vector<int> book, int target)
{
// 2-pointer approach
sort(book.begin(), book.end());
int left = 0, right = n-1;
while (left < right) {
int sum = book[left] + book[right];
if (sum == target)
return "YES";
else if (sum < target)
left++;
else
right--;
}
return "NO";
}
102 views
0 replies
1 upvote
Interview problems
Solution for Two sum problem in Java
public class Solution {
public static String read(int n, int []book, int target){
// Write your code here.
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(book[i]+book[j]==target){
return "YES";
}
}
}
return "NO";
}
}
62 views
0 replies
0 upvotes
Interview problems
Java easy approach for TWO SUM
//Java easy approach for TWO SUM
import java.util.Arrays;
import java.util.HashMap;
public class Solution {
public static String read(int n, int []nums, int target){
// Write your code here.
Arrays.sort(nums);
int i=0,j=n-1;
// String ans="NO";
while(i<j){
int sum=nums[i]+nums[j];
if(sum < target) i++;
else if(sum > target) j--;
else return "YES";
}
return "NO";
}
}
//please upvote
27 views
0 replies
0 upvotes
Interview problems
Java HashSet Solution
I took help of chatgpt ..
import java.util.*;
public class Solution {
public static String read(int n, int []book, int target){
// Write your code here.
HashSet<Integer> map = new HashSet<>();
for(int i = 0; i < n; i++){
int currentElement = book[i];
int requiredElement = target - currentElement;
if(map.contains(requiredElement)){
return "YES";
}
map.add(currentElement);
}
return "NO";
}
}
37 views
0 replies
0 upvotes
Interview problems
Most Easiest JAVA Solution
public class Solution {
public static String read(int n, int[] book, int target) {
// Loop through the array
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) { // j starts from i+1 to avoid using the same element twice
if (book[i] + book[j] == target) { // Check if the sum of book[i] and book[j] equals the target
return "YES"; // Return "yes" if the target is found
}
}
}
return "NO"; // Return "no" if no such pair is found after checking all elements
}
}
65 views
0 replies
0 upvotes
Interview problems
better than 100%
string read(int n, vector<int> book, int target)
{
int l=0;
int r=n-1;
sort(book.begin(),book.end());
while(l<r){
int sum=book[l]+book[r];
if(sum==target){
return "YES";
}
else if (sum<target){
l++;
}
else{
r--;
}
}
return "NO";
}
63 views
1 reply
1 upvote
Interview problems
Sorting + 2 pointer approach
#include "bits/stdc++.h";
string read(int n, vector<int> book, int target)
{
// Write your code here.
sort(book.begin(),book.end());
int left = 0;
int right = book.size()-1;
while(left<right){
if(book[left]+book[right]==target){
return "YES";
}else if(book[left]+book[right]<target){
left++;
}else{
right--;
}
}
return "NO";
}
54 views
0 replies
1 upvote
1
2
3
4
C++ (g++ 5.4)
Console