0

I have to find a unique number in unsorted array, but my function returns wrong number, I can't understand why. Here is my code:

function findUniq(arr) {
  let sorted = [...arr].sort();
  if (sorted.length === 0) return 0;
  // do magic
  let num = 0;
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[num] !== sorted[i]) {
      num++;
      sorted[num] = sorted[i];
    }
  }
  return num + 1;
}

const testArray = [9, 7, 7, 9, 6, 6, 5, 5, 5];
console.log(findUniq(testArray));

if I invoke findUniq([9,7,7,6,6,5,5,5]) it gives 4. What do I do wrong? Thanks in advance. I forgot to mention I have to have just one for loop to implement O(n) time complexity

PCDSandwichMan
  • 1,964
  • 1
  • 12
  • 23
zulfiya
  • 81
  • 7
  • 1
    What number it should return – Exception Aug 23 '22 at 18:19
  • 2
    What steps have you taken to debug this code? – Andy Aug 23 '22 at 18:19
  • @Andy I console.log(num) in different places of code, tried to start i = 0 I'm not super good debugger because I am beginner and learn algorithms at the moment. – zulfiya Aug 23 '22 at 18:23
  • @Exception should return 9 but returns 4 but the array has no 4. I am very confused – zulfiya Aug 23 '22 at 18:24
  • 2
    Does this answer your question? [How to find non repeated numbers in an Array using JavaScript?](https://stackoverflow.com/questions/50854750/how-to-find-non-repeated-numbers-in-an-array-using-javascript) – Hydrothermal Aug 23 '22 at 18:27
  • @Hydrothermal it solves but I have to have one for loop in the task. Any way I will try hat way, thank you. – zulfiya Aug 23 '22 at 18:30
  • Try executing it step by step, either in a full debugger or in the [Python Visualizer](https://t1p.de/xfk5o) (yes it supports JS also) because it's simpler to use and will also allow stepping back in time. It will help you understand what's going on. – CherryDT Aug 23 '22 at 18:36
  • No answer in the potential duplicate satisfies the req of being a single O(n) loop. – danh Aug 23 '22 at 19:13

4 Answers4

0

This should work:

It returns only one unique number in array or undefined

If you want all unique numbers replace return arr[0] with return arr. It will then return array of all unique numbers (or empty array if there are not any)

function findUniq(arr) {
    arr.filter((item, index) => {
        arr.splice(index, 1)
        const unique = !arr.includes(item)
        arr.splice(index, 0, item)
        return unique
    })

    return arr[0]
}

ES6 aproach:

function findUniq(arr) {
    return arr
        .map((c) => arr.filter((b) => c == b))
        .filter((e) => e.length < 2)
        .reduce((total, cur) => total.concat(cur), [])
}
Hostek
  • 509
  • 3
  • 9
  • it will not pass my tests because I have to use just one loop. But why my function returns number 4 if in the passed array I don't have that number? – zulfiya Aug 23 '22 at 18:40
0

You can use reduce and can find the item that repeats once in the last index.

var arr = [9,7,7,6,6,5,5,5]
var uniqueNumber;
arr.reduce((obj,val,index) => 
{
    obj[val] ? ++obj[val] : obj[val] = 1;
    if(index == (arr.length - 1))
    {
      uniqueNumber = Object.keys(obj).find(key => obj[key] === 1)
    }
    return obj
},{})
console.log(uniqueNumber)
Okan Karadag
  • 2,542
  • 1
  • 11
  • 23
  • I like it, but by iterating the reduce accumulator in every pass, it's O(n*m), where n is the input length and m is the number of unique elements in the input. – danh Aug 23 '22 at 19:03
0

To do it in a single O(n) loop, reduce, keeping track of counts as well as a set of singular items.

function findUniq(arr) {
    let [single] = arr.reduce((acc, el) => {
      if (!acc[el]) acc[el] = 0;
      if (++acc[el] === 1) acc.singular.add(el);
      else acc.singular.delete(el);
      return acc;
    }, { singular: new Set() }).singular;
    return single;
  }
  
  const input = [2, 2, 9, 7, 7, 6, 6, 5, 5, 5];
  const result = findUniq(input);
  console.log(result);
danh
  • 62,181
  • 10
  • 95
  • 136
0

I don't know why your solution doesn't work, but here is working code:

const arr = [9,9,7,7,8,6,1,6,5,5,5]

function findUnique(arr){
  const sorted = [...arr].sort()
  
  if(sorted[0] !== sorted[1]) return sorted[0]
  
  if(sorted[sorted.length - 1] !== sorted[sorted.length - 2]) return sorted[sorted.length - 1]
  
  for(let i = 0; i < sorted.length; i++){
    if(sorted[i] !== sorted[i - 1] && sorted[i] !== sorted[i + 1]) return sorted[i]
  }
  
  return "no unique"
}

console.log(findUnique(arr))
deaponn
  • 837
  • 2
  • 12