Two Sum

Easy
0/40
Average time to solve is 15m
profile
Contributed by
211 upvotes
Asked in companies
DelhiveryErnst & Young (EY)Bank of New York Mellon (BNY Mellon)

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