• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

March 24, 2014 by Dhaval Dave

Given an array A[] and a number x, check for pair in A[] with sum as x

Write a C program that, given an array A[] of n numbers and another number x, determines whether or not there exist two elements in S whose sum is exactly x.
There can be several ways to do, what we found are two methods.

1 ) Using Sort input Array
2) Using Hash Map


Algorithm with Example with Sorting Array

findPair (A[], sum)  
//A = {1, 4, 6, 9, -3 , 12, 2}
//sum = 10 
1) len = Length of A[]
//len = 8 
2) Sort the array in increasing order.
//A = {-3,1,2,3,4,6,9,12} 
3) Initialize two variables on starting and ending 
 (a) Initialize first to the leftmost index: lt = 0
       (b) Initialize second  the rightmost index:  rt = len-1  
                   
4) Loop while lt < rt.
       (a) If (A[l] + A[r] == sum)  then return 1
       (b) Else if( A[l] + A[r] <  sum )  then lt++
       (c) Else rt--

//First Iteration: 
//a)lt=0 , rt=7 , -3+12 != 10
//b)-3+12 = 9 < 10 =>; lt=lt++ =>; lt = 1.
//Second Iteration : 
//a) lt=1, rt =7 , 1+12 !=10
//b) 1+12 =13 > 10, =>; rt=len-1=>; rt=6
//Third Iteration : 
//a)lt=1, rt=6 , 1+9 =10 =>; Return 1.

5) No candidates in whole array : return 0

Time Complexity : O(nlogn) (for merge if Merge or Heap sort is used.)
Space Complexity : O(n)( for Merge sort) O(1) for heap sort.

Algorithm with Example for Using Hash map 

Let A be the given array.
And X be the give sum

len = A.length
for i=0 to len{
  hash(A[i]) = i  // key is the element and value is its index.
}
//Hash is created with index and element.

for i=0 to len{
  if hash(X - A[i]) != j  // if (X - element) exists and is different we found a pair
    {
     print "pair i , j has sum K"
    }//if

}//for

Searching in Hash takes O(1).
So what we do is
take first element and if its counter number which makes sum X exists then print both number.
example

A = {-3,1,2,3,4,6,9,12}
A[0] = -3 
What we search in condition if hash(X - A[i]) != i
if(10-(-3))=13 exist for some 'j' then 
element at i (=-3)  and j(=13) makes sum 10.

Time Complexity : O(N)
Space Complexity : O(N) for storing Hash.

Similar Articles

Filed Under: Adobe Interview Questions, Flipkart Interview Questions, Interview Questions, problem Tagged With: Array, Sorting

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Regular Expression Matching

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

Check Binary Tree is Binary Search Tree or not

Minimum insertions to form a palindrome

BlueStone E-commerce Interview Experience

Linked List V/S Binary Search Tree

Daughter’s Age VeryGood Puzzle

Find Percentage of Words matching in Two Strings

Reliance Jio Software Developer Interview Experience

Find loop in Singly linked list

DFS (Depth First Search)

Find the element that appears once others appears thrice

Max Sum in circularly situated Values

Coin Collection Dynamic Programming

Count Possible Decodings of a given Digit Sequence

Wrong Directions given find minimum moves so that he can reach to the destination

Given a string, find the first character which is non-repetitive

25 horses 5 tracks Find 3 fastest puzzle

Generate largest number arranging a no. of given non negative integer numbers

Cisco Hiring Event 21st – 22nd Feb 2015

Test Cases for Round Function

Circular Linked List

Find Pythagorean Triplets in an array in O(N)

Apriori algorithm C Code Data Mining

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Common Ancestor in a Binary Tree or Binary Search Tree

The greedy coins game Dynamic Programming

Difference between a LinkedList and a Binary Search Tree BST

Hackerearth : Counting Subarrays

Longest Increasing Subsequence

Copyright © 2023 · Genesis Framework · WordPress · Log in