Find all pair of Array of Integers whose sum is equal to a given number in C#

It’s been a long time since I was trying to solve this problem. Whenever I tried I couldn’t solve it. I always miss some boundary conditions or something else. But today finally I solved it and it’s funny because approach is quite simple and I was trying code like building time machine ūüėõ

Array : [2, 4, 3, 5, 6, -2, 4, 7, 8, 9]
Given sum : 7
pairs whose sum is equal to value : 7
(2, 5) , (4, 3) , (-2, 9)

Array : [0, 14, 0, 4, 7, 8, 3, 5, 7]
Sum : 11
pairs whose sum equals: 11
(7, 4) , (3, 8) , (7, 4)

Array : [10, 9, 5, 9, 0, 10, 2, 10, 1, 9]
Sum : 12
pairs whose sum equals 12
(2, 10)

There are two ways of doing this,

Method 1: Brute Force approach – use two nested loops and make a pair and compare sum of them with given number. Its time complexity would be O(n^2).

Method 2: In this method we loop over the array only once. For each item of array, subtract this item from given number and if array item doesn’t exist in our list then add it otherwise print this item and subtraction of array item and given number. Its time complexity would be O(n) as we loop over only once and comparison are also less.

Code in C#:

static void Main(string[] args)
{
    int[] arr = { 0, 14, 0, 4, 7, 11,8, 3, 5, 7 };
    int n = 11;
    PrintPairs(arr, n);
    Console.ReadKey();
}
 
private static void PrintPairs(int[] arr, int n)
{
    var arrayItemList = new List<int>();
    foreach (var item in arr)
    {
        int remainingvalue = n - item;
        if (arrayItemList.Contains(remainingvalue))
        {
            Console.WriteLine($"({ item},{remainingvalue})");
        }
        else
        {
            arrayItemList.Add(item);
        }
    }
}

Reverse an Integer Array without using extra space in C#

Our approach is to solve this problem without traversing whole array. So we keep two variables, one is set to start item of an array and another is set to end item of an array.and we move both of them simultaneously. So, in n/2 iterations we completely traverse the array.

Time complexity = O(n)

        static void Main(string[] args)
        {
            int[] arr = { 61, 19, 34, 83, 123, 97 };
            Reverse(arr);
            foreach (var item in arr)
            {
                Console.WriteLine(item);
            }
            Console.ReadKey();
        }

        static void Reverse(int[] arr)
        {
            if (arr.Length == 0 || arr.Length == 1)
            {
                return;
            }
            else
            {
                int start = 0, end = arr.Length - 1, temp = 0;
                while (start < end)
                {
                    temp = arr[end];
                    arr[end] = arr[start];
                    arr[start] = temp;
                    ++start;
                    --end;
                }
            }
        }

Our task is to find top two integers from an integer array. For example:

Array: []

Output: Invalid Input

Array: [-1]

output: Max1: -1, Max2: -1

Array: [2,18]

Output: Max1: 2, Max2: 18

Array:[15, 45, 34, 100, -456, 432, 2, 1000]

Output: Max1: 1000, Max2: 432

Code in C#:

 class FindTopTwoIetemsFromUnSortedArray
    {
        static void Main(string[] args)
        {
            int[] arr = { 12342,-162361,12342};
            FindTopTwoMaxIntegers(arr);
            Console.ReadKey();
        }

        static void FindTopTwoMaxIntegers(int[] arr)
        {
            if (arr == null || arr.Length == 0)
            {
                Console.WriteLine("Invalid input");
            }
            else
            {
                int max1 = int.MinValue, max2 = int.MinValue;
                foreach (int item in arr)
                {
                    if (item >= max1)
                    {
                        max2 = max1;
                        max1 = item;
                    }
                    else if (item <item > max2)
                    {
                        max2 = item;
                    }
                }

                if (max2 == int.MinValue)
                {
                    max2 = max1;
                }

                Console.WriteLine($"Max1:{max1}, Max2: {max2}");
            }
        }
    }

Sum of all proper divisors of a natural number in O(n)

Suppose you have a natural number say 20, you need to find out sum of its divisors. How will you start?

Input: number = 20

Output: 22

As we all know that a proper divisor can’t be greater than number/2. Also a prime divisor can’t be greater than Squar Root of the number. So now we have two approaches to compute above sum:

Method1 – Logic is, a proper divisor can’t be greater than number/2. This logic is preety simple but you have to loop till number/2. So suppose number is 100, then we have to iterate 50 times. Time complexity is O(n).

Step1: Loop till condition i <= number/2 is true.
Step2: Check foe proper divisors
Step3: Sum all the proper divisor.

Input: 20
Output: 1 + 2 + 4 + 5 + 10 = 22

class SumOfAllProperDivisors
 {
       static void Main(string[] args)
       {
             Console.Write("Please enter a number: ");
             int num = Convert.ToInt32(Console.ReadLine());
             int sum = 0;
             for (int i = 1; i <= num/2; ++i)
             {
                    if (num % i == 0)
                    {
                          sum += i;
                    }
            }
            Console.WriteLine($"Divisor sum: {sum}");
            Console.ReadKey();
      }
 }

Method2 – Logic is,¬†a prime divisor can’t be greater than Squar Root of the number. In this case our loop iteration will be considerabily less in compare to Method1. Time complexity is O(n).

Step1: Loop till condition i <= Squar root of number is true.
Step2: Check for proper divisor.
Step3: if it is proper divisor then add this number to our result.
Step3.1: Check for the Quotient, if it is not same as divisor and divisor is not equal to 1 then add quotient to our result.

Input: 20
Output: 1 + (2 + 10) + (4 + 5) = 22

class SumOfAllProperDivisors
 {
     static void Main(string[] args)
     {
           Console.Write("Please enter a number : ");
           int num = Convert.ToInt32(Console.ReadLine());
           int sum = 0;
           for (int i = 1; i <= Math.Sqrt(num); ++i)
           {
                  if (num % i == 0)
                  {
                        sum += i;
                        if ((num / i != i) && i != 1)
                        {
                               sum += (num / i);
                        }
                   }
            }
            Console.WriteLine($"Divisor sum: {sum}");
            Console.ReadKey();
     }
 }

Find Two Missing Numbers in O(n)

Given an array of n unique integers where each element in the array is in range [1, n]. The array is not necessarily sorted and has all distinct elements. The task is to find missing numbers if there is any.

Input  : {10, 5, 8, 1}
Output : 2, 3, 4, 6, 7, 9

Input : {3, 2, 4}
Output : 1 

Input : arr[] = {1, 2}
Output :

Algorithm: As array is not sorted so we first add all the items into dictionary (because reading is index based and quite fast).

Step1: Loop over the array and add all the items to our dictionary. Dictionary will have array items as KEY and if item is present in array then Value would be TRUE else FALSE.

Step2: Find the greatest item of the array.

Step3: Loop from 1 to the max item of the array

Step4. For each iteration of the loop, check whether this number is present in our Dictionary. if not present then print this number, otherwise skip.

class FindTwoMissingNumbers
    {
        static void Main(string[] args)
        {
            /// Input array
            int[] arr = { 10, 2, 8, 6, 5 };
 
            /// Temporary container. Array item will be our KEY and Value
            /// would be if TRUE that means item is not missing, FALSE 
            /// means item is missing so print this item.
            /// 
            Dictionary<int, bool> dict = new Dictionary<int, bool>();
 
            /// Add all the array items to this container. Array item 
            /// will be our KEY and value would be TRUE for all the items.
            for (int i = 0; i < arr.Length; ++i)
            {
                dict.Add(arr[i], true);
            }
 
            /// Loop from 1 to n (nth item of the array, i.e. max item of the array)
            int maxItem = arr.Max(x => x);
            for (int i = 1; i <= maxItem; ++i)
            {
                /// If a number is not present that means this is missing item
                /// so print it
                if (!dict.ContainsKey(i))
                {
                    Console.WriteLine(i);
                }
            }
 
            Console.ReadKey();
        }
    }

 

Check if string follows order of characters defined by a pattern or not.

Given an input string and a pattern, check if characters in the input string follows the same order as determined by characters present in the pattern. Assume there won’t be any duplicate characters in the pattern.

Examples:

Input: string = "engineers rock", pattern = "er";
Output: true
All 'e' in the input string are before all 'r'.

Input: string = "engineers rock", pattern = "egr";
Output: false
There are two 'e' after 'g' in the input string.

Input: string = "engineers rock", pattern = "gsr";
Output: false
There are one 'r' before 's' in the input string.

Algorithm: The approach is quite simple. Please follow the below steps:

Step1: First get a new filtered string from input string that has same characters as pattern.

1.1. Loop over all the characters of the input string.
1.2. Check whether a input string’s character matches with any character of pattern.
1.3. If there are any consecutive characters then add only one character to our filtered list. To do so, use a char type variable and match it with current variable, if matches then skip otherwise add current character to our filtered list.

Step2: Filtered list has only same number of characters as our pattern, if not then return FASLE, if yes then match all the characters. If there is any character that doesn’t match in the same sequence as pattern then return false otherwise return TRUE.

We are done now. Lets see the actual implementation of the above algorithm.

class StringPatternMatching
{
  static void Main(string[] args)
  {
    Console.WriteLine(IsStringFollowThePattern("engineers rock", "er"));
    Console.WriteLine(IsStringFollowThePattern("engineers rock", "egr"));
    Console.WriteLine(IsStringFollowThePattern("engineers rock", "gsr"));
    Console.WriteLine(IsStringFollowThePattern("engineers rock", "eger"));
    Console.ReadKey();
  }
 
  static bool IsStringFollowThePattern(string input, string pattern)
  {
    var filteredInputCharacters = new List<char>();
    char previousChar = default(char);
    /// Loop over the input string to get only pattern matching 
    /// characters
    foreach (var item in input)
    {
      /// Check for the pattern characters, if match then go
      if (pattern.Contains(item))
      {
         /// If there are consecutive duplicate characters then add 
         /// only one, skip rest. If previous character is same as 
         /// current character then skip otherwise add it to our
         /// filtered list.
         if (previousChar != item)
         {
            filteredInputCharacters.Add(item);
            previousChar = item;
         }
       }
     }
 
     /// Filtered list has only same number of characters as our pattern, 
     /// if not then return FASLE, if yes then match all the characters.
     /// If there is any character that doesn't match in the same sequence 
     /// as pattern then return false otherwise return TRUE.
     for (int i = 0; i < filteredInputCharacters.Count; ++i)
     {
       if (filteredInputCharacters[i] != pattern[j])
       {
         return false;
       }
     }
 
     return true;
   }
}

 

 

 

 

 

 

Remove extra spaces from a string in C#

Problem source: http://www.geeksforgeeks.org/remove-extra-spaces-string/

The problem is to remove extra spaces from the string, from beginning of the string,
from end of the string and between words. But for special character like “.”, “,”, “?”
there should not be any space before them. Time complexity should be O(n).

Input: ”    Hi   ,   this is test string       input.   What do you think it’ll  work    ?    ”
Output: “Hi, this is test string input. What do you think it’ll  work?”

 class RemoveExtraSpacesFromAString
    {
        static void Main(string[] args)
        {
            string input = ”    Hi   ,   this is test string       input.   What do you think it’ll  work    ?    “;
            bool isPreviousCharSpace = false, isFirstCharFound = true;
            foreach (var ch in input)
            {
                if (ch != ‘ ‘)
                {
                    if (isPreviousCharSpace)
                    {
                        if (ch == ‘.’ || ch == ‘?’ || ch == ‘,’ || isFirstCharFound)
                        {
                            Console.Write(ch);
                        }
                        else
                        {
                            Console.Write(string.Concat(” “, ch));
                        }
                        isPreviousCharSpace = false;
                    }
                    else
                    {
                        Console.Write(ch);
                    }

                    isFirstCharFound = false;
                }
                else
                {
                    isPreviousCharSpace = true;
                }
            }
            Console.ReadKey();
        }
    }