Find element that appears odd number of times

Question

I'm trying to solve this exercise of finding the number that appears an odd number of times in an array. I have this so far but the output ends up being an integer that appears an even number of times. For example, the number 2 appears 3 times and the number 4 appears 6 times, but the output is 4 because it counts it as appearing 5 times. How can it be that it returns the first set that it finds as odd? Any help is appreciated!

         function oddInt(array) {
         var count = 0;
         var element = 0;
         for(var i = 0; i < array.length; i++) {
           var tempInt = array[i];
           var tempCount = 0;
             for(var j = 0; j <array.length; j++) {
                if(array[j]===tempInt) {
                tempCount++;
                  if(tempCount % 2 !== 0 && tempCount > count) {
                  count = tempCount; 
                  element = array[j];
                }
               }
              }
             }
           return element;
           }
           oddInt([1,2,2,2,4,4,4,4,4,4,5,5]);

Answer 1

function findOdd(numbers) {
  var count = 0;
  for(var i = 0; i<numbers.length; i++){
    for(var j = 0; j<numbers.length; j++){
      if(numbers[i] == numbers[j]){
        count++;
      }
    }
    if(count % 2 != 0 ){
      return numbers[i];
    }
  }
};

console.log(findOdd([20,1,-1,2,-2,3,3,5,5,1,2,4,20,4,-1,-2,5])); //5
console.log(findOdd([1,1,1,1,1,1,10,1,1,1,1])); //10

Answer 2

First find the frequencies, then find which ones are odd:

const data = [1,2,2,2,4,4,4,4,4,4,5,5]
const freq = data.reduce(
  (o, k) => ({ ...o, [k]: (o[k] || 0) + 1 }), 
  {})
const oddFreq = Object.keys(freq).filter(k => freq[k] % 2)

// => ["1", "2"]

Answer 3

If we are sure only one number will appear odd number of times, We can XOR the numbers and find number occurring odd number of times in n Comparisons.XOR of two bits is 1 if they are different else it will be 0. Truth table is below.

A   B   A^B
0   0    0
0   1    1
1   0    1
1   1    0

So when we do XOR of all the numbers, final number will be the number appearing odd number of times. Let's take a number and XOR it with the same number(Appearing two times). Result will be 0 as all the bits will be same. Now let's do XOR of result with same number. Now result will be that number because all the bits of previous result are 0 and only the set bits of same number will be set in the result. Now expanding it to an array of n numbers, numbers appearing even number of times will give result 0. The odd appearance of the number result in that number in the final result.

func oddInt(numbers: [Int]) -> Int {
var result = 0
for aNumber in numbers {
  result = result ^ aNumber
}
return result
}

Answer 4

Here is a solution with O(N) or O(N*log(N))

function findOdd(A) {
    var count = {};
    for (var i = 0; i < A.length; i++) {
        var num = A[i];
        if (count[num]) {
            count[num] = count[num] + 1;
        } else {
            count[num] = 1;
        }
    }
    var r = 0;
    for (var prop in count) {
        if (count[prop] % 2 != 0) {
            r = prop;
        }
    }
    return parseInt(r); // since object properies are strings
}

Answer 5

 #using python
 a=array('i',[1,1,2,3,3])
 ans=0
 for i in a:
     ans^=i
 print('The element that occurs odd number of times:',ans)
 
  

 

1. List item output:

   The element that occurs odd number of times: 2

   Xor(^)operator when odd number of 1's are there,we can get a 1 in the output
   Refer Xor Truth table: https://www.electronicshub.org/wp-content/uploads/2015/07/TRUTH-TABLE-1.jpg

Answer 6

function oddInt(array) {
  // first: let's count occurences of all the elements in the array
  var hash = {};                 // object to serve as counter for all the items in the array (the items will be the keys, the counts will be the values)
  array.forEach(function(e) {    // for each item e in the array
    if(hash[e]) hash[e]++;       // if we already encountered this item, then increments the counter
    else hash[e] = 1;            // otherwise start a new counter (initialized with 1)
  });
  
  // second: we select only the numbers that occured an odd number of times
  var result = [];               // the result array
  for(var e in hash) {           // for each key e in the hash (the key are the items of the array)
    if(hash[e] % 2)              // if the count of that item is an odd number
      result.push(+e);           // then push the item into the result array (since they are keys are strings we have to cast them into numbers using unary +)
  }
  return result;
}
console.log(oddInt([1, 2, 2, 2, 4, 4, 4, 4, 4, 4, 5, 5]));

Return only the first:

function oddInt(array) {
  var hash = {};
  array.forEach(function(e) {
    if(hash[e]) hash[e]++;
    else hash[e] = 1;
  });
  
  for(var e in hash) { // for each item e in the hash
    if(hash[e] % 2)    // if this number occured an odd number of times
      return +e;       // return it and stop looking for others
  }
  // default return value here
}
console.log(oddInt([1, 2, 2, 2, 4, 4, 4, 4, 4, 4, 5, 5]));

Answer 7

That happens because you are setting the element variable each time it finds an odd number, so you are setting it when it find one, three and five 4.

Let's check the code step by step:

function oddInt(array) {
    // Set the variables. The count and the element, that is going to be the output
    var count = 0;
    var element = 0;

    // Start looking the array
    for(var i = 0; i < array.length; i++) {
        // Get the number to look for and restart the tempCount variable
        var tempInt = array[i];
        var tempCount = 0;
        console.log("");
        console.log(" * Looking for number", tempInt);
        // Start looking the array again for the number to look for
        for(var j = 0; j <array.length; j++) {
            // If the current number is the same as the one that we are looking for, sum it up
            console.log("Current number at position", j, "is", array[j]);
            if(array[j]===tempInt) {
                tempCount++;
                console.log("Number found. Current count is", tempCount);
                // Then, if currently there are an odd number of elements, save the number
                // Note that you are calling this altough you don't have looped throgh all the array, so the console will log 3 and 5 for the number '4'
                if(tempCount % 2 !== 0 && tempCount > count) {
                    console.log("Odd count found:", tempCount);
                    count = tempCount;
                    element = array[j];
                }
            }
        }
    }
    return element;
}
oddInt([1,2,2,2,4,4,4,4,4,4,5,5]);

What we want to do is to check for the count AFTER looping all the array, this way:

function oddInt(array) {
    // Set the variables. The count and the element, that is going to be the output
    var count = 0;
    var element = 0;

    // Start looking the array
    for(var i = 0; i < array.length; i++) {
        // Get the number to look for and restart the tempCount variable
        var tempInt = array[i];
        var tempCount = 0;
        console.log("");
        console.log(" * Looking for number", tempInt);
        // Start looking the array again for the number to look for
        for(var j = 0; j <array.length; j++) {
            // If the current number is the same as the one that we are looking for, sum it up
            console.log("Current number at position", j, "is", array[j]);
            if(array[j]===tempInt) {
                tempCount++;
                console.log("Number found. Current count is", tempCount);
            }
        }
        // After getting all the numbers, then we check the count
        if(tempCount % 2 !== 0 && tempCount > count) {
            console.log("Odd count found:", tempCount);
            count = tempCount;
            element = tempInt;
        }
    }
    return element;
}
oddInt([1,2,2,2,4,4,4,4,4,4,5,5]);

By the way, this is only for you to understand where was the problem and learn from it, although this is not the most optimized way of doing this, as you may notice that you are looking for, let's say, number 2 three times, when you already got the output that you want the first time. If performance is part of the homework, then you should think another way :P

Answer 8

This is because your condition if(tempCount % 2 !== 0 && tempCount > count) is true when the 5th 4 is checked. This updates the count and element variables.

When the 6th 4 is checked, the condition is false.

To fix, move the condition outside the innermost loop so that it's checked only after all the numbers in the array are counted.

Answer 9

function oddInt(array, minCount, returnOne) {
  minCount = minCount || 1;
  var itemCount = array.reduce(function(a, b) {
    a[b] = (a[b] || 0) + 1;
    return a;
  }, {});
  /*
  itemCount: {
    "1": 1,
    "2": 3,
    "4": 6,
    "5": 2,
    "7": 3
  }
  */
  var values = Object.keys(itemCount).filter(function(k) {
    return itemCount[k] % 2 !== 0 && itemCount[k]>=minCount;
  });
  
  return returnOne?values[0]:values;
}

var input = [1, 2, 2, 2, 4, 4, 4, 4, 4, 4, 5, 5, 7, 7, 7];

console.log(oddInt(input, 3, true));
console.log(oddInt(input, 1, true));
console.log(oddInt(input, 2, false));

Answer 10

"A" is the array to be checked.

function findOdd(A) {
    var num;
    var count =0;
    for(i=0;i<A.length;i++){
       num = A[i]
       for(a=0;a,a<A.length;a++){
          if(A[a]==num){
          count++;
          }
     } if(count%2!=0){
          return num;
     }
   }
}

Answer 11

function oddOne (sorted) {
  let temp = sorted[0];
  let count = 0;
  for (var i = 0; i < sorted.length; i++) {
    if (temp === sorted[i]) {
      count++;
      if (i === sorted.length - 1) {
        return sorted[i];
      }
    } else {
      if (count % 2 !== 0) {
        return temp;
      }

      count = 1;
      temp = sorted[i];
    }
  }
}

Answer 12

function oddInt(array) {
    let result = 0;
    for (let element of array) {
        result ^= element
    }
    return result
}

Answer 13

var oddNumberTimes = (arr) => {
  let hashMap = {};

  for (let i = 0; i < arr.length; i++) {
    hashMap[arr[i]] = hashMap[arr[i]] + 1 || 1;
  }

  for (let el in hashMap) {
    if (hashMap[el] % 2 !== 0) {
      return el;
    }
  }

  return -1;
};

Answer 14

You can use bitwise XOR:

function oddInt(array) {
  return array.reduce(function(c, v) {
    return c ^ v;
  }, 0);
}
console.log(oddInt([20, 1, -1, 2, -2, 3, 3, 5, 5, 1, 2, 4, 20, 4, -1, -2, 5]) == 5);
console.log(oddInt([1, 1, 1, 1, 1, 1, 10, 1, 1, 1, 1]) == 10);

Answer 15

Had to implement a solution for a similar problem and here it is:

function findtheOddInt(A) {
let uniqueValues = [...new Set(A)]; // Get the unique values from array A
const odds = [];
uniqueValues.forEach(element => {
    const count = A.reduce((acc, cur) => cur === element ? acc + 1: acc, 0) // count the occurrences of the element in the array A
    if (count % 2 === 1) {
        odds.push(element);
    }
});
return odds[0]; // Only the first odd occurring element

}

Answer 16

Logic that you written has time complexity theta(n^^2) as it involves two loops i.e one outer loop and one inner loop. One of the mistake I can see in the code is below code

if(tempCount % 2 !== 0 && tempCount > count) {
                  count = tempCount; 
                  element = array[j];  

You have written it inside the inner loop which is wrong. Right logic should be when inner loop finishes which means it has checked how many times (count) number appears in the array. Now check for even or odd count using modulus operator.

We can achieve this solution even using Xor Operator as it has two properties which can solve it in theta(n) times.

1. Property 1: When one XOR 0 and number, then answer is number.
2. Property 2: When one XOR number with itself, then answer is 0.

Let us use this property to find the odd occurred element in the array

array = [1, 1, 2]
res = 0
for i in array:
    res =  res ^ i
print("Odd occurred element is, res)

Answer 17

var arr=[1,2,2,2,2,3,4,3,3,3,4,5,5,9,9,10];

var arr1=[];

for(let i=0;i

 {
    var count=0;

    for(let j=0;j<arr.length;j++)

     {
        if(arr[i]==arr[j])

        {

           count++;
        }
      }

     if(count%2 != 0 )

        {

           arr1.push(arr[i]);
         }
  }

console.log(arr1);