• 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

BlueStone E-commerce Interview Experience

Facebook Interview Question : Interleave List

Cisco Hiring Event 21st – 22nd Feb 2015

Print all nodes that are at distance k from a leaf node

Apriori algorithm C Code Data Mining

Find and print longest consecutive number sequence in a given sequence in O(n)

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

Binary Tree in Java

Find next greater number with same set of digits

Find Percentage of Words matching in Two Strings

Implement LRU Cache

Find if a binary tree is height balanced ?

Reverse a Linked List in groups of given size

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

Python Array String

VMWare Openings

Python List

How strtok() Works

Client Server C program

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

HackeEarth Flipkart’s Drone

SAP Off Campus Hiring_ March 2015 Sample Questions

building with N steps, we can take 1,2,3 steps calculate number of ways to reach at top of building

Advanced SQL Injection

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

System Design: Designing a LLD for Hotel Booking

Trapping Rain Water

Find Nearest Minimum number in left side in O(n)

simple sql injection

Coin Collection Dynamic Programming

Copyright © 2025 · Genesis Framework · WordPress · Log in