• 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

The greedy coins game Dynamic Programming

Generate next palindrome number

Find min element in Sorted Rotated Array (Without Duplicates)

Generic Object Oriented Stack with Template

SAP Hiring Off-Campus General Aptitude

Daughter’s Age VeryGood Puzzle

Possible sizes of bus to carry n groups of friends

How strtok() Works

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

Amazon Interview On-Campus For Internship – 1

flattens 2 D linked list to a single sorted link list

Sequence Finder Dynamic Programming

Skiing on Mountains Matrix

Implement a generic binary search algorithm for Integer Double String etc

LeetCode: Binary Tree Maximum Path Sum

1014 Practice Question of New GRE – Princeton

Handle duplicates in Binary Search Tree

Longest Increasing Subsequence

Find Percentage of Words matching in Two Strings

Amazon Interview Experience – SDE Chennai

SAP Off Campus Hiring_ March 2015 Sample Questions

Search element in a matrix with all rows and columns in sorted order

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

Find min element in Sorted Rotated Array (With Duplicates)

Difference between a LinkedList and a Binary Search Tree BST

C Program for TAIL command of UNIX

robot standing at first cell of an M*N matrix. It can move only in two directions, right and down. In how many ways, it can reach to the last cell i.e. (M, N) Code it

Maximum difference between two elements s.t larger element appears after the smaller number

Test Cases for Round Function

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

Copyright © 2025 · Genesis Framework · WordPress · Log in