0
\$\begingroup\$

this is a function given an array of numbers to find the one that appears an odd number of times.

what I did is:

  • Sort the array
  • Check if the array is odd.
  • If the array length is 1 then return this value.
  • Assign every two values to a new array, and check if it is a number.
  • Check if every two values are equals.
  • If not equals then the result will be the first element on the new array
function findOdd(A) {
  
  let copA = Array.from(A).sort((a, b) => a - b);
  let res = 0;

  if (copA.length % 2 === 0) return;
  if (copA.length == 1) return res = copA[0];
    
  let newArr = [];
  for (let i in copA) {
    // if not a integer break
    if (!Number.isInteger(copA[i])) {
      res = 0;
      break;
    };

    newArr.push(copA[i]);
    if(newArr.length == 2) {
      const [a,b] = newArr;
      if (a === b) {
        newArr = [];
      } else {
        res = a;
        newArr[0] = b;
        break;
      }
    } else if (newArr.length == 1) {
        res = newArr[0];
    }
  }
  return res;
}

// test the code
findOdd([20,1,-1,2,-2,3,3,5,5,1,2,4,20,4,-1,-2,5]); // 5
findOdd([1,1,2,-2,5,2,4,4,-1,-2,5]); // -1
findOdd([20,1,1,2,2,3,3,5,5,4,20,4,5]); // 5
findOdd([10]); // 10
findOdd([1,1,1,1,1,1,10,1,1,1,1]); // 10
findOdd([5,4,3,2,1,5,4,3,2,10,10]); // 1

My code works well, but I looking to improve it.

\$\endgroup\$
5
  • 3
    \$\begingroup\$ If all numbers are safe integer, use bitwise xor should solve your question most effectivly. If not, use DataView.prototype.setFloat64() and DataView.prototype.getBigUint64() as workaround may convert them to (big) integers, and you may apply xor on them. Although I don't quite like the second approach, since it is too tricky. \$\endgroup\$
    – tsh
    Jan 25 '21 at 9:10
  • \$\begingroup\$ Ah, as a note, bitwise xor tricky only works if the given array is known to be valid (1 and only 1 odd number in it.) \$\endgroup\$
    – tsh
    Jan 25 '21 at 9:24
  • \$\begingroup\$ @tsh You should write that as an answer rather than as a comment. \$\endgroup\$ Jan 25 '21 at 9:26
  • 4
    \$\begingroup\$ [20,1,-1,2,-2,3,3,5,5,1,2,4,20,4,-1,-2,5].reduce((set, value) => set.delete(value) ? set : set.add(value) , new Set()).values().next().value \$\endgroup\$
    – RoToRa
    Jan 25 '21 at 9:26
  • \$\begingroup\$ @200_success But OP didn't mentioned the detail requirement of I/O. For example, if the I/O require function throw a exception if no / multiple odd numbers, you cannot use bitwise tricky. \$\endgroup\$
    – tsh
    Jan 25 '21 at 10:01
1
\$\begingroup\$

Review and Complexity

This answer is in two parts.

  1. A review of the code and a rewrite based on the review. There are what might be bugs. This addressed in the second part.
  2. A look at complexity, how to reduce complexity. An example function is given with lower complexity.

Review

  • Do not use un-delimited code blocks eg if (copA.length == 1) return res = copA[0]; should be if (copA.length == 1) { return res = copA[0]; }

  • Use === (Strict equality) rather than == (Equality) The same would apply for !== (Strict inequality) rather than != (Inequality)

  • Avoid using for...in without checking if the key is a property or index of the array/object you are iterating. Use for...of for arrays and if the item being iterated is an object use Object.keys to create an array of property names.

  • Use const for variables that do not change. Eg the array copA never changes and should be a const.

    On the same point it is preferred to use const when possible, If you use newArr.length = 0 rather than newArr = [] you can then make newArr a const. This is also more efficient at run time as zeroing an array is quicker than creating a new array.

  • The general rule for line ends is use a semicolon only when ASI (Automatic Semicolon Insertion) is ambiguous (The assumption is you may not know what the next line of code is eg when using bundlers, pre-parse parser, anything that changes the code before parsing).

    A } that delimits a code block is an unambiguous line terminator and does not require a semicolon.

    A } at the end of a object literal can be ambiguous and does requires a semicolon.

  • Most comments are just code noise, often they assume the reader does not know how to read code.

    Comments that are a Human readable expressions of intent should be avoided.

    If you find that some code is a little hard to understand from just reading the code it is likely that some renaming and or restructuring will make your intent clear rather than having to explain your intent with a comment

Use modern syntax.

To copy an array use the spread operator ...(Spread syntax) rather than Array.from

Names

Names should be what the value represents rather than its type.

  • A (for array) can be values or numbers The plural means its an array

  • copA function arguments are not constants and you can reuse them. See rewrite.

  • Across many languages we use i, j, and sometimes k as counters. You should only use these names when they are counters. The loop for (let i in copA) { should use a name that represent what the value holds. Eg for (let num in copA) { or for (let val in copA) {

Efficient code

Always be efficient and avoid redundancy.

  • The line return res = copA[0] is a redundant assignment and should be return copA[0]

  • The second else if(newArr.length == 1) { is not required and can just be else {

  • Array.push returns the length of the array after the push.

    Chrome, Edge, Nodejs and many APPs that use JS engines use V8. V8 has a quirk that makes indexed references eg newArr.length slower than direct or immediate references. Thus it would be better to use the statement if (newArr.push(copA[i]) === 2) {`` rather than if(newArr.length == 2)`

    Please note that this is trivial and as such would be something to you do when you are comfortable with your coding knowledge.

  • Don't use arrays to count occurrences . See rewrite. Because I see this type of thing so often will boldly yell 'DON'T USE A ARRAYS TO GET COUNTS'

  • The line newArr[0] = b; is followed by a break thus you never use the array newArr again making the assignment redundant.

Rewrite

The rewrite does not create a new algorithm. It behaves the same as you code and passes the provided tests. This does not mean it will do so on all tests but I am limited by only what you provide.

The rewrite is just a clean up of the code in regards to the points outlined above.

  • The array use to count numbers has been replaced with a counter.
  • To keep the previous value a variable called prevNum is used.
  • As prevNum is the value you return via res, res has been removed with prevNum.

The code

    function findOdd(numbers) {
        let count = 0, prevNum;
        numbers = [...numbers].sort((a, b) => a - b);
        if (numbers.length % 2 === 0) { return }
        if (numbers.length === 1) { return numbers[0] }
      
        for (const num of numbers) {
            if (Number.isInteger(num)) {
                if (num === prevNum) {
                    count ++;
                } else if (prevNum !== undefined) {
                    if (count % 2) { break }
                    count = 1;
                    prevNum = num;
                } else {
                    count ++;
                    prevNum = num;
                }
            } else { return 0 }
        }
        return prevNum;
    }
    

Complexity

This problem has a complexity of \$O(n)\$.

Your code has a complexity of \$O(n log( n))\$. Why? because you sort the array. Sorts are complex. If you can avoid using a sort do so.

I understand the reasoning behind the use of a sorted array, to group numbers.

We must find a better way to group values but first your code has some inconsistent results (or bugs?)

Bugs???

Note: that in the rewrite (above) I pointed out that it only passed the tests provided. Any working code provides all that is needed to rewrite it and pass any test. However I strongly suspect that you have bugs that are not detected by the tests you provided.

Test are useless if they do not check every edge case. Edge cases are more often than not the source of bugs. Just looking at the code an I see inconsistency in the return values.

Inconsistencies

The inconsistent results due to

  • The early return of even sized arrays.
  • The early break if a non integer is found.
  • The problems description is incomplete as it does not clearly state what should be returned in some edge cases

These Inconsistencies mean that the following inputs give or (may be giving) unexpected results

findOdd([1,0.1,2,1,0.1])); // returns 0, would expect 2?
findOdd([0.1,1]));         // returns undefined, would expect 1?
findOdd([0.1,1,1]));       // returns 0, The return has not been defined

There are also 2 unexplained return values, each the contra of the other

  1. Returning the first and lowest value if the array length is 1. Why the lowest?
  2. Returning zero. Why zero and not the lowest as above?

Reducing complexity

I will reduce the complexity to \$O(n)\$ by using a hash map to count groups. JS provides several hash maps Map, Set, WeakMap and WeakSet. Only the first two can help in this case as Number is not a referenced value. (exception when number is created using Number(123))

First some assumptions

I must make some assumptions about how it behaves in edge cases.

  • Even sized arrays may still contain odd groups of values.
  • If there are no odd groups the first integer value is returned.
  • If there are no integer values or the array is empty undefined is returned.
  • All values in the array are of type Number

Steps

An explanation of the new solution

Create a hash map to count occurrences in each group.
Iterate each value in input, 
   If a value is an integer 
       If the values is in the map add one to the count
       If not in the map add to the map with a count of 1
Iterate the completed map. 
   If an entry is an odd count return that maps value as the result
If the size of the hash map is zero return undefined
return the first value in the hash map.

Getting the first entry from a hash map can be done using [...map.keys()][0] however that is is overly complex \$O(n)\$. Rather you can use the iterator protocols Iteration protocols next().value with a complexity of \$O(1)\$

The \$O(n)\$ solution

function findOdd(numbers) {
    const groupsByVal = new Map();
    for (const num of numbers) {
        if (Number.isInteger(num)) {
            const counter = groupsByVal.get(num);
            if (counter) { 
                counter.count ++;
            } else { 
                groupsByVal.set(num, {count: 1});
            }
        }
    }
    for (const [num, {count}] of groupsByVal.entries()) {
        if (count % 2) { 
            return num;
        }
    }
    return groupsByVal.keys().next().value;
}

Or I prefer

function findOdd(numbers) {
    const grpByVal = new Map();
    for (const num of numbers) {
        if (num % 1 === 0) {
            const grp = grpByVal.get(num);
            if (grp) { grp.c ++ }
            } else { grpByVal.set(num, {c: 1}) }
        }
    }
    for (const [num, {c}] of grpByVal.entries()) {
        if (c % 2) { return num }
    }
    return grpByVal.keys().next().value;
}
\$\endgroup\$
4
  • \$\begingroup\$ You may use a Set, and simply delete an element from Set if the set already has it. \$\endgroup\$
    – tsh
    Jan 26 '21 at 7:16
  • \$\begingroup\$ "if the array length is 1", then the only value in array does occurr odd times. \$\endgroup\$
    – tsh
    Jan 26 '21 at 8:08
  • \$\begingroup\$ @tsh An input array length of 1 does not mean that the array item is an integer. It is more efficient to use a map and count items. Add and delete cycles on the same item can thrash memory management adding overhead \$\endgroup\$
    – Blindman67
    Jan 26 '21 at 9:54
  • \$\begingroup\$ "does not mean that the array item is an integer". It is yet another edge case here (since OP didn't really state what should be happened for edge cases) \$\endgroup\$
    – tsh
    Jan 26 '21 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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