CSharp.AlgorithmsAndDataStructures/DataStructures/Algorithms/Problems/MinimumSumPair.cs at master · leodeg/CSharp.AlgorithmsAndDataStructures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
using System;

namespace DA.Algorithms.Problems
{
    public static class MinimumSumPair
    {
        /// <summary>
        /// Find a two elements such that their sum is closest to zero.
        /// <para>Time Complexity - O(n^2)</para>
        /// </summary>
        ///
        /// <exception cref="System.ArgumentException" />
        /// <exception cref="System.ArgumentNullException" />
        public static int[] MinSumPair (int[] array)
        {
            if (array == null)
            {
                throw new System.ArgumentNullException ();
            }

            if (array.Length < 2)
            {
                throw new System.ArgumentException ("Array must have at least two elements.");
            }

            int[] result = new int[2];
            int absSum = 0;
            int minSum = Math.Abs (array[0] + array[1]);
            int front = 0;
            int end = 0;

            for (front = 0; front < array.Length - 1; front++)
            {
                for (end = front + 1; end < array.Length; end++)
                {
                    absSum = Math.Abs (array[front] + array[end]);
                    if (absSum < minSum)
                    {
                        minSum = absSum;
                        result[0] = array[front];
                        result[1] = array[end];
                    }
                }
            }
            return result;
        }

        /// <summary>
        /// Find a two elements such that their sum is closest to zero.
        /// <para>Time Complexity - O(n)</para>
        /// </summary>
        ///
        /// <exception cref="System.ArgumentException" />
        /// <exception cref="System.ArgumentNullException" />
        public static int[] MinSumPairUsingSorting (int[] array)
        {
            if (array == null)
            {
                throw new System.ArgumentNullException ();
            }

            if (array.Length < 2)
            {
                throw new System.ArgumentException ("Array must have at least two elements.");
            }

            Array.Sort (array);
            int[] result = new int[2];
            int absSum = 0;
            int minSum = Math.Abs (array[0] + array[1]);
            int front = 0;
            int end = array.Length - 1;

            while (front < end)
            {
                absSum = Math.Abs (array[front] + array[end]);
                if (absSum < minSum)
                {
                    minSum = absSum;
                    result[0] = array[front];
                    result[1] = array[end];
                }

                if (absSum < 0) ++front;
                else if (absSum > 0) --end;
                else break;
            }
            return result;
        }
    }
}