Two Sum

Easy
0/40
Average time to solve is 15m
profile
Contributed by
212 upvotes
Asked in companies
DelhiveryAmerican ExpressErnst & Young (EY)

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.
Output format: 
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

Mapping of books ?

Approaches (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)

  1. Create a hash map ‘mp’, mapping integer to boolean.
  2. 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.
  3. 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
Full screen
Console