Skip to main content

Given an array of integers, and a target value determine if there are two integers that add to the sum using C#

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.
        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++)
            {
                for (int j = i + 1; j < A.Length; j++)
                {
                    if (A[i] + A[j] == sum)
                    {
                        isFound = true;
                        break;
                    }
                }
            }

            return isFound;
        }


        //solution 2. 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);

            while (leftIndex < rightIndex)
            {
                if (Arr[leftIndex] + Arr[rightIndex] == sum)
                {
                    isFound = true;
                    break;
                }
                else if (Arr[leftIndex] + Arr[rightIndex] < sum)
                {
                    leftIndex++;
                }
                else
                    rightIndex--;
            }

            return isFound;
        }


        //Solution 3 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++)
            {
                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);
                quickSorting(Arr, pivot + 1, 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);
            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);


            startTime = DateTime.Now;
            bool resultFromSorting = ExampleOfTwoSome.TwoSumUsingSorting(Arr, Arr.Length, sum);
            Console.WriteLine("{0} :This Array has Two Candidates :{1} of sum :{2} in time ={3}", Arr, resultFromSorting,sum, DateTime.Now - startTime);


            startTime = DateTime.Now;
            bool resultFromHashSet = ExampleOfTwoSome.TwoSumUsingHashSet(Arr, Arr.Length, sum);
            Console.WriteLine("{0} :This Array has Two Candidates :{1} of sum :{2} in time ={3}", Arr, resultFromHashSet,sum, DateTime.Now - startTime);

            Console.WriteLine(superDigit("148", 3));


            Console.WriteLine("Please click <enter> to exit");
            Console.ReadLine();
        }


Output :

Comments

Popular posts from this blog

Git fundamental and useful command to use - version-2

      Install Git your local machine Link: Git - Downloads (git-scm.com) Version : git version 2.31.1.windows.1   Know the version $ git --version   Git help for command $ git help config $ git config --help Prompt the git config help file in browser Make a directory $ mkdir shubhapp$ mkdir shubhapp $ cd shubhapp/ - go to directory   initialize the git $ git init Initialized empty Git repository in C:/Users/shubh/shubhapp/.git/   Create a file Hello.txt   Add this file to git $ git Add hello.txt   Commit the changes $ git commit -a -m "commit comment"   Connect to remote github $ git config --global user.username shubh-techie  

Min Cost to Connect Ropes problem solution using PriorityQueue using C#

Given n ropes of different lengths, we need to connect these ropes into one rope. We can connect only 2 ropes at a time. The cost required to connect 2 ropes is equal to sum of their lengths. The length of this connected rope is also equal to the sum of their lengths. This process is repeated until n ropes are connected into a single rope. Find the min possible cost required to connect all ropes. Input: ropes = [ 8 , 4 , 6 , 12 ] Output: 58 Explanation: The optimal way to connect ropes is as follows 1. Connect the ropes of length 4 and 6 (cost is 10 ). Ropes after connecting: [ 8 , 10 , 12 ] 2. Connect the ropes of length 8 and 10 (cost is 18 ). Ropes after connecting: [ 18 , 12 ] 3. Connect the ropes of length 18 and 12 (cost is 30 ). Total cost to connect the ropes is 10 + 18 + 30 = 58 public static void Demo() { //int[] Ropes = { 4, 3, 2, 6 }; //int[] Ropes = { 8, 4, 6, 12 }; int[] Ropes = { 1, 2, 5, 10, 35, 89