• 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

Test Cases for Round Function

Word Break Problem

Get K Max and Delete K Max in stream of incoming integers

25 horses 5 tracks Find 3 fastest puzzle

Possible sizes of bus to carry n groups of friends

Introduction To Number Theory ( Part 1 )

SAP Interview Questions

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Get Minimum element in O(1) from input numbers or Stack

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

Daughter’s Age VeryGood Puzzle

Cisco Hiring Event 21st – 22nd Feb 2015

Trapping Rain Water

Calculate price of parking from parking start end time prices

Find the kth number with prime factors 3, 5 and 7

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

Adobe Interview Questions 8 month Exp

Urban Ladder Written Test.

Sort an array according to the order defined by another array

SAP Off Campus Hiring_ March 2015 Sample Questions

ADOBE Aptitude C Language Test

Given Set of words or A String find whether chain is possible from these words or not

Find position of the only set bit

1014 Practice Question of New GRE – Princeton

Knight Tour Problem (Graph – Breadth First Search)

Singly linked list

The greedy coins game Dynamic Programming

SAP Off Campus Hiring_ March 2015 Verbal Skills

Count number of ways to reach a given score in a game

Find min element in Sorted Rotated Array (Without Duplicates)

Copyright © 2025 · Genesis Framework · WordPress · Log in