Given an array of integers, and a target value determine if there are two integers that add to the sum.
Example 1: Let Array be: {4,2,6,5,7,9,10} and sum to find be :13
Output: true
Example2 : Let Array be {1, 4, 45, 6, 10, -8} and sum to find be 16
Output: true
//Solution 1: using looping all pair of
elements.
elements.
public static bool TwoSumUsingLoopingAllItems(int[] A, int arr_size, int sum)
{
if (arr_size < 0)
return false;
bool isFound = false;
for (int i = 0; i
< A.Length; i++)
< A.Length; i++)
{
for (int j = i +
1; j < A.Length; j++)
1; j < A.Length; j++)
{
if (A[i] + A[j] == sum)
{
isFound = true;
break;
}
}
}
return isFound;
}
//solution 2.
using arrary sorting
using arrary sorting
public static bool TwoSumUsingSorting(int[] Arr, int arr_size, int sum)
{
if (arr_size < 0)
return false;
bool isFound = false;
int leftIndex = 0, rightIndex = arr_size – 1;
quickSorting(Arr, leftIndex,
rightIndex);
rightIndex);
while (leftIndex < rightIndex)
{
if (Arr[leftIndex] + Arr[rightIndex] == sum)
{
isFound = true;
break;
}
else if
(Arr[leftIndex] + Arr[rightIndex] < sum)
(Arr[leftIndex] + Arr[rightIndex] < sum)
{
leftIndex++;
}
else
rightIndex–;
}
return isFound;
}
//Solution 3
using hashset
using hashset
public static bool TwoSumUsingHashSet(int[] Arr, int arr_size, int sum)
{
if (arr_size < 0)
return false;
bool isFound = false;
HashSet<int> TrackingPair = new HashSet<int>();
for (int i = 0; i
< arr_size; i++)
< arr_size; i++)
{
int otherPair = sum – Arr[i];
if (TrackingPair.Contains(otherPair))
{
isFound = true;
break;
}
TrackingPair.Add(otherPair);
}
return isFound;
}
public static void quickSorting(int[] Arr, int left, int right)
{
if (left < right)
{
int pivot = getPivotOfArray(Arr, left, right);
quickSorting(Arr, left, pivot –
1);
1);
quickSorting(Arr, pivot + 1,
right);
right);
}
}
private static int getPivotOfArray(int[] arr, int left, int right)
{
int tempPivotNumber = arr[right];
int pivotIndex, j;
pivotIndex = left – 1;
for (j = left; j <= right; j++)
{
if (arr[j] <= tempPivotNumber)
{
pivotIndex++;
//Swapping the ith and jth element
int temp = arr[pivotIndex];
arr[pivotIndex] = arr[j];
arr[j] = temp;
}
}
return pivotIndex;
}
Test all the function:
class Program
{
static void Main(string[] args)
{
int[] Arr = { 4, 2, 6, 5, 7, 9, 10 };
int sum = 13;
bool result = ExampleOfTwoSome.TwoSumUsingLoopingAllItems(Arr,Arr.Length,
sum);
sum);
DateTime startTime = DateTime.Now;
Console.WriteLine(“{0} :This Array has Two Candidates :{1} of sum :{2} in
time ={3}”, Arr,result,sum,DateTime.Now-
startTime);
time ={3}”, Arr,result,sum,DateTime.Now-
startTime);
startTime = DateTime.Now;
bool resultFromSorting = ExampleOfTwoSome.TwoSumUsingSorting(Arr,
Arr.Length, sum);
Arr.Length, sum);
Console.WriteLine(“{0} :This Array has Two Candidates :{1} of sum :{2} in
time ={3}”, Arr, resultFromSorting,sum,
DateTime.Now – startTime);
time ={3}”, Arr, resultFromSorting,sum,
DateTime.Now – startTime);
startTime = DateTime.Now;
bool resultFromHashSet = ExampleOfTwoSome.TwoSumUsingHashSet(Arr,
Arr.Length, sum);
Arr.Length, sum);
Console.WriteLine(“{0} :This Array has Two Candidates :{1} of sum :{2} in
time ={3}”, Arr, resultFromHashSet,sum,
DateTime.Now – startTime);
time ={3}”, Arr, resultFromHashSet,sum,
DateTime.Now – startTime);
Console.WriteLine(superDigit(“148”, 3));
Console.WriteLine(“Please click <enter> to exit”);
Console.ReadLine();
}
Output :
