Unable to solve Lonely Number problem in O(n) time

Question

In a given array of numbers, one element will show up once and the rest will show up twice. Can you find that number in O(n) linear time?

eg - lonelyNumber([4, 4, 6, 1, 3, 1, 3]) // 6

I am trying this in javascript and my code so far -

var lonelyNumber=function(arr) {   
  for(var i=0;i<arr.length;i++) {
    for(var j=0;j<arr.length;j++) {
      if(j!==i && arr[i]===arr[j]) {
        break;
      }
    }
    if(j===arr.length) {
      return arr[i];
    }
  }
}

console.log(lonelyNumber([4, 4, 6, 1, 3, 1, 3]));

But this is having a complexity of O(n^2). How do I get it to O(n)?

Hint: use a dictionary to store already seen numbers. – Willem Van Onsem Sep 21 '19 at 12:52 — Willem Van Onsem, Sep 21 '19 at 12:52
I will google for dictionary store and try it out – Vaishak Sep 21 '19 at 13:00 — Vaishak, Sep 21 '19 at 13:00
Just XOR all elements, That is your answer. – nice_dev Sep 21 '19 at 13:01 — nice_dev, Sep 21 '19 at 13:01

score 1 · Accepted Answer · answered Sep 21 '19 at 12:52

1

You can use hashmap for this. And the way to do that is using Objects in javascript.

Basically I am looping through the array and adding new keys if the object is found first time and removing keys if the object is found second time. In the end the only key left in the object is the result.

var lonelyNumber=function(arr) {
  var obj={};
  for(var i=0;i<arr.length;i++) {
    if(obj[arr[i]]) {
      delete obj[arr[i]];
    } else {
      obj[arr[i]]=true;
    }
  }
  return Object.keys(obj)[0];
}

This should result in complexity of O(n).

answered Sep 21 '19 at 12:52

Nithin Kumar Biliya

2,763
3
34
54

thanks. But how is object being a hask map? – Vaishak Sep 21 '19 at 13:01
refer to [this](https://stackoverflow.com/a/8877719/1298824) – Nithin Kumar Biliya Sep 21 '19 at 13:03

Unable to solve Lonely Number problem in O(n) time

1 Answers1