Last Updated: 10 Nov, 2022
Two Sum
Easy
Asked in companies
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.
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.
Approaches
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”