5
\$\begingroup\$

In an array of integers find all the pairs of elements whose sum is even and form a new array consisting of these sums.

Could you tell me whether my code is ok or not?

using System;
using System.Collections.Generic;
using static System.Net.Mime.MediaTypeNames;
using System.Collections.Generic;

namespace General
{
    class Program   {            

        public static int[] GetPairs(int[] InitialArray)
        {
            HashSet<int> tmp = new HashSet<int>();

            for (int i = 0; i < InitialArray.Length; i++) {
                for (int j = 0; j < InitialArray.Length; j++) {
                    if (i == j) {
                        continue;
                    }

                    int first = InitialArray[i];
                    int second = InitialArray[j];

                    if ((first + second) % 2 == 0) {
                        tmp.Add(first + second);
                    }

                }
            }

            return tmp.ToArray();
        }
        static void Main(string[] args)
        {
            int[] InitialArray = new int[] { 1, 3, 5, 7, 9 };

            Console.WriteLine(string.Join(", ", GetPairs(InitialArray)));
            
        }
    }
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ If readability is important I will consider using moreLinQ, and Source.SubSet(2).Where(p=> p.Sum() ..) . \$\endgroup\$ Jul 19, 2023 at 6:45

4 Answers 4

5
\$\begingroup\$

Your code is easily readable but it does a bit too much work.

You are iterating n² times so you calculate every sum twice and then you use a Hashset to deduplicate. For more efficiency, run the loops like this:

for (int i = 0; i < InitialArray.Length - 1; i++) {
    for (int j = i+1; j < InitialArray.Length; j++) {

So that you cut the iterations in half.

A further optimization would be to split the numbers into odd and even beforehand. As even sums can only result from 2 even numbers or 2 odd ones, you can split the work and combine them again:

    public static int[] GetPairs(int[] InitialArray)
    {
        var split = InitialArray.ToLookup(x => x % 2 == 0);
        var even = split[true].ToList();
        var odd = split[false].ToList();

        var sums = PairwiseSums(even);
        sums.UnionWith(PairwiseSums(odd));
        return sums.ToArray();

        static HashSet<int> PairwiseSums(List<int> list)
        {
            var result = new HashSet<int>();
            for (int i = 0; i < list.Count- 1; i++)
            {
                for (int j = i + 1; j < list.Count; j++)
                {
                    result.Add(list[i] + list[j]);
                }
            }
            return result;
        }
    }

This avoids odd sums outright. It might be faster for large arrays but it could be harder to understand.

\$\endgroup\$
6
  • \$\begingroup\$ spliting odd and even can be done in one go with a ToLookUp(x => x % 2 ). It will not be the most readable access to odd or even list but at least ToLookup doesnt care about unknown key. \$\endgroup\$ Jul 19, 2023 at 6:39
  • 1
    \$\begingroup\$ Yes, the only issue with that was that ILookup returns only IEnumerable so I could not access it via index. But ToLookup should save one list iteration. \$\endgroup\$ Jul 19, 2023 at 9:54
  • \$\begingroup\$ @DragandDrop: Doesn't x % 2 in C# return -1 for negative odd numbers like -5, like it does in C and C++? So you want x % 2 != 0 to detect odd numbers, because x % 2 == 1 will be false. Or split based on the low bit of their bit-pattern, if C# guarantees 2's complement (or you don't mind assuming it), like x & 1 to get a 0 or 1 integer according to odd vs. even. The problem statement doesn't promise non-negative integers, and the code is using a signed type. \$\endgroup\$ Aug 10, 2023 at 22:55
  • \$\begingroup\$ @PeterCordes, First, thank you! You are right (msdn), and I just learned something. It's been around 20 years, and no one has brought that to my attention. Stack Overflow is full of x%2==1, and mechanically, I always tested with ==0, so I must have known at some point. \$\endgroup\$ Aug 11, 2023 at 6:24
  • 1
    \$\begingroup\$ Thanks for the reminder, I fixed the code example. With ToLookup() the only check needed is == 0 so I changed it to that one as well. \$\endgroup\$ Aug 11, 2023 at 13:11
3
\$\begingroup\$

Could you tell me whether my code is ok or not?

If you know it works, then sure, it is OK.


Simplification Insights

  • Initialize the j relative to i then increment in synch
  • i index must stop as one less than j. It is j that needs to watch for the end of the array. No need to test if i=j
  • Thinking about the nature, so to say, of patterns and/or singular exceptions to the rules (program requirements).
    • odd + even is the only odd sum situation. Testing true or false for this "exception" had me review truth tables, and BAM! I found exclusive OR

    • Think of XOR as returns true only iff (if and only if) one is true and the other false. This maps perfectly to the odd/even pair situation.

.

HashSet<int> evenSums = new HashSet<int>();

for (int i = 0; i < InitialArray.Length - 1; i++) {
  for (int j = i+1 < InitialArray.Length; j++)  {

    if !( (InitialArray[i] % 2 == 0) ^ (InitialArray[j] % 2 == 0) )
       evenSums.Add(InitialArray[i] + InitialArray[j]);  
  
  } // j 
} // i

return evenSums.ToArray();

After Thoughts

  • Name things for what they are not how they are implemented
    • The name evenSums means I don't have to do mental math to know the purpose of the loop.
    • evenSums communicates intent. If the code did not add to even sums I know there is a mistake somewhere.
    • InitialArray must be renamed too.
  • You say all even sums go into the result set. But HashSet implies otherwise. Your program requirements should state that. I am not being picky here. Conflicting code and comments/requirements will fail code review in the real world. Here, I must make assumptions that will drastically affect how I evaluate this HashSet.
\$\endgroup\$
6
  • \$\begingroup\$ If you're going to use XOR, why not XOR the original integers and check the low bit? On booleans, it's just a !=, like x_even != y_even. If I was going to write that if condition, I might write if (x_even == y_even) where x_even is an expression like (InitialArray[i] % 2 == 0), and y_even is the same expression but with j. Or I'd write int tmp = InitialArray[i] + InitialArray[j]; if (tmp % 2 == 0) evenSums.Add(tmp); because addition and bitwise XOR have the same effect on the low bit, and are equally cheap in real CPUs. (And the problem was defined in terms of even sum) \$\endgroup\$ Aug 10, 2023 at 23:04
  • \$\begingroup\$ (Fun fact: bitwise XOR of integers is add without carry. That's precisely why the low bit comes out the same. en.wikipedia.org/wiki/Adder_(electronics) - either look at a half-adder, or full-adder with carry-in = 0, and note that the output is just XOR of the input bits.) \$\endgroup\$ Aug 10, 2023 at 23:07
  • \$\begingroup\$ "If you're going to use XOR, why not XOR the original integers and check the low bit?" -> I prefer quantum tunneling but .NET doesn't have a library for that. \$\endgroup\$
    – radarbob
    Aug 10, 2023 at 23:07
  • \$\begingroup\$ Wait what? You can't write x ^ y to do bitwise XOR on int variables in C#? learn.microsoft.com/en-us/dotnet/csharp/language-reference/… says ^ is a bitwise XOR for the integral numeric types. Only with bool operands does it act as a logical XOR which evaluates both inputs to a boolean before XORing. (I don't program in C#, so it's possible there's something I'm missing, but I'd find it very weird for a C-derived language to not provide bitwise XOR.) \$\endgroup\$ Aug 10, 2023 at 23:08
  • \$\begingroup\$ Regardless, it's probably more efficient to just add with +, since you want the + result if the sum is even, so out of two equally efficient ways to test if the sum will be even, the one that also actually computes the sum as part of that will save work when it is needed. \$\endgroup\$ Aug 10, 2023 at 23:14
2
\$\begingroup\$

I am going to assume you are a beginner and that this may be school work. Is your code okay? In that it produces the correct results, yes. However, regarding first and foremost its efficiency, and secondly its style, the answer is no to both of those.

Quick side note: the answer set just coincidentally is in ascending order. That has nothing to do with your code, and just so happens to be that way because the input array of integers coincidentally is in ascending order itself.

Coding Style and Variable Names

Let's cover the trivial things first. One, in C#, the preferred placement of opening braces is a new line.

Two, local variable names should begin with a lowercase, not uppercase letter as you have. More to the point, the names of variables could be spelled out and/or clarified better.

Good use for HashSet

I do credit you for using a HashSet to hold the unique results. Very good for you. As others have mentioned, you are looping too frequently, and there is a simple "hack" to get an even sum: the 2 numbers must both be even or both be odd. Another way to look at that is both numbers must have the same modulus or remainder with % 2.

Other Efficiency Opportunities

Unless the homework directions explicitly asked for an integer array, you do not need to take the extra step to of using .ToArray().

As mentioned by other, the way you construct your inner loop could be improved by having your j start at i + 1.

You could employ the hack mentioned earlier. The other examples, however, take time and memory to create more lists, when they are not really needed. You can still use the hack with a minimum of looping over the arrays, and with a minimum of operations being performed. Below I offer my improvements of all of the above and include a bonus GetPairs2 method:

using System;
using System.Collections.Generic;

namespace General
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] wholeNumbers = new int[] { 1, 3, 5, 7, 9 };
            Console.WriteLine(string.Join(", ", GetPairs(wholeNumbers)));
        }

        public static HashSet<int> GetPairs(int[] wholeNumbers)
        {
            HashSet<int> resultSet = new HashSet<int>();

            for (int index1 = 0; index1 < wholeNumbers.Length - 1; index1++)
            {
                int firstRemainder = wholeNumbers[index1] % 2;
                for (int index2 = index1 + 1; index2 < wholeNumbers.Length; index2++)
                {
                    if (firstRemainder == (wholeNumbers[index2] % 2))
                    {
                        resultSet.Add(wholeNumbers[index1] + wholeNumbers[index2]);
                    }
                }
            }

            return resultSet;
        }

        public static IEnumerable<int> GetPairs2(IList<int> wholeNumbers)
        {
            HashSet<int> resultSet = new HashSet<int>();

            for (int index1 = 0; index1 < wholeNumbers.Count - 1; index1++)
            {
                int firstRemainder = wholeNumbers[index1] % 2;
                for (int index2 = index1 + 1; index2 < wholeNumbers.Count; index2++)
                {
                    if (firstRemainder == (wholeNumbers[index2] % 2))
                    {
                        if (resultSet.Add(wholeNumbers[index1] + wholeNumbers[index2]))
                        {
                            yield return wholeNumbers[index1] + wholeNumbers[index2];
                        }
                    }
                }
            }
        }
    }
}

Notice I use longer, specific names such as wholeNumbers or index1.

GetPairs now returns HashSet<int>. It tries to use a minimum of operations, and Remainder operator uses a very fast operation.

Bonus Method

For a bonus, the GetPairs2 allows for the input to be a list or array, as long as it supports the IList<int> interface. And the results are streamed to you thanks to IEnumerable<int>. Granted that this yields little performance boost for such a small sample set. But if you had millions of numbers, this would be a noticeable performance benefit while using less memory.

Other Considerations

If you are a beginner, then my guess is the lesson is about looping within a loop. If you are a bit beyond a beginner, then there are more things to consider.

We talked about efficiency in how to minimize the number of operations and loop iterations. One way to spark this train of thought is to ask what happens if the input list had a million elements?

There are other things to wonder about the inputs. Can some elements be negative? Is there a constraint on their value? What is the array was { int.MaxValue, int.MaxValue } ? There sum would be even and should be included, but with the default integer wraparound, there sum is actually -2. If you wanted their actual magnitude, then the return collection should not be int, but rather should be long.

\$\endgroup\$
2
  • \$\begingroup\$ As you brought up namming, GetPairs nor GetPairs2 hint that they return a source into chunks of 2. Not the odds sum of all possible subset of 2, without duplicate. But I can't figure a good name for it tho. Not without spliting the pairing and the sum. \$\endgroup\$ Jul 19, 2023 at 6:56
  • \$\begingroup\$ @DragandDrop Very fair point. I agree and I also was stumped at a better name. Perhaps: GetEvenSum or SumPairsToEvenNumber. \$\endgroup\$
    – Rick Davin
    Jul 19, 2023 at 13:47
-1
\$\begingroup\$

Your code is already quite good! you could do to make it even better:

  1. Use a HashSet instead of a List to store the sums: Using a HashSet instead of a List will ensure that you don't add duplicate sums to the result array.

  2. Use a nested loop instead of two separate loops: You can use a nested loop instead of two separate loops to simplify your code.

Here's an updated version of your code that incorporates these changes:

public static int[] GetPairs(int[] InitialArray)
{
    HashSet<int> tmp = new HashSet<int>();

    for (int i = 0; i < InitialArray.Length; i++) {
        for (int j = i + 1; j < InitialArray.Length; j++) {[
            int sum = InitialArray[i] + InitialArray[j];
            if (sum % 2 == 0) {
                tmp.Add(sum);
            }
        }
    }

    return tmp.ToArray();
}

\$\endgroup\$
1
  • 4
    \$\begingroup\$ OPs code already uses a HashSet, and nested loops. \$\endgroup\$
    – harold
    Jul 16, 2023 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.