2

I am trying to build logic currently with arrays and data structure. I am trying to implement the logic using for loop

function getRepeatingNumber(arr) {

  for (var i = 0; i < arr.length; i++) {
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        return arr[i];
      }
    }
  }
  return undefined;
}
getRepeatingNumber([2, 3, 6, 5, 2]);

the above function takes in array and returns a repeated item in the array so in the above case it will return 2. But what if I have an array something like this arr[2,3,3,6,5,2] in this case it should return 3 but as the outer loop has index [0] which is 2 as the reference it will return 2 as the answer.

How to implement a function that returns the first occurrence of the repeated item.

James Z
  • 12,209
  • 10
  • 24
  • 44
jsLearner
  • 159
  • 3
  • 11
  • So you got to change your logic so it does not exit on the first match – epascarello Feb 08 '19 at 14:41
  • Create a "memory" of all the items you've seen so far, each iteration check with that memory if that item has been seen, if not add to the memory, else exit/return from the loop at that time. – Danilo Cabello Feb 08 '19 at 14:46
  • I have first decided to push the item in an empty array if the item does not match with the next entry but then got stuck if the item which already pushed in an array has found a match at the end of the input array. – jsLearner Feb 08 '19 at 14:58

3 Answers3

5

Instead of iterating with j in the part after i, iterate the part before i:

function getRepeatingNumber(arr){
    for (var i = 1; i < arr.length; i++) {
        for (var j = 0; j < i; j++) {
            if (arr[i] === arr[j]) {
                return arr[i];
            }
        }
    }
}
console.log(getRepeatingNumber([2,3,3,6,5,2]));

Note that an explicit return undefined is not needed, that is the default behaviour already.

You could also use indexOf to shorten the code a bit:

function getRepeatingNumber(arr){
    for (var i = 1; i < arr.length; i++) {
        if (arr.indexOf(arr[i]) < i) {
            return arr[i];
        }
    }
}
console.log(getRepeatingNumber([2,3,3,6,5,2]));

You could even decide to make use of find -- which will return undefined in case of no match (i.e. no duplicates in our case):

function getRepeatingNumber(arr){
    return arr.find((a, i) => {
        if (arr.indexOf(a) < i) {
            return true;
        }
    });
}
console.log(getRepeatingNumber([2,3,3,6,5,2]));

If you do this for huge arrays, then it would become important to have a solution that runs with linear time complexity. In that case, a Set will be useful:

function getRepeatingNumber(arr){
    var set = new Set;
    return arr.find(a => {
        if (set.has(a)) return true;
        set.add(a);
    });
}
console.log(getRepeatingNumber([2,3,3,6,5,2]));

And if you are into functions of functions, and one-liners, then:

const getRepeatingNumber = r=>(t=>r.find(a=>[t.has(a),t.add(a)][0]))(new Set);
console.log(getRepeatingNumber([2,3,3,6,5,2]));
trincot
  • 317,000
  • 35
  • 244
  • 286
1

You need a data structure to keep track of first occurring index.

My recommendation is to use an array to store all the index of repeating numbers. Sort the array in ascending order and return the item at first index from the array.

function getRepeatingNumber(arr){
 var resultIndexArr = [];
 var count = 0;
 var flag = 0;
 for(var i=0;i<arr.length;i++)
 {
  for(var j=i+1;j<arr.length;j++)
   {
    if(arr[i] === arr[j])
    {
  flag = 1;
  resultIndexArr[count++] = j;
    }
   }
 }
 
 resultIndexArr.sort((a, b) => a - b);
 
 var resultIndex = resultIndexArr[0];
 if(flag === 1)
  return arr[resultIndex];
 else
  return;
}

console.log(getRepeatingNumber([2,3,6,5,2])); // test case 1
  
console.log(getRepeatingNumber([2,3,3,6,5,2])); // test case 2

console.log(getRepeatingNumber([2,5,3,6,5,2])); // test case 3

This will return correct result, but this is not the best solution. The best solution is to store your items in an array, check for each iteration if the item already exists in your array, if it exists then just return that item.

user1579234
  • 501
  • 5
  • 15
  • 1
    Good job! Many before you got it wrong ;-) Note that `if(flag === 0)` is not necessary, as that is the only possibility left (it will always be true when the execution gets there) – trincot Feb 08 '19 at 15:08
  • One issue: `sort` will sort alphabetically, but you need a numerical sort. Look at this [Q&A](https://stackoverflow.com/questions/1063007/how-to-sort-an-array-of-integers-correctly) – trincot Feb 08 '19 at 15:20
  • Thank you for the answer, but don't you think we are making it more difficult and increasing the code to solve this. Creating a data structure to store the item and then sort to return the item where we can easily just loop in the item and return the first occurrence of it. Well I thought about it by creating a new data structure and to store the values, however I am keeping the time and space complexity in mind to solve the problems. I am quite new in coding and data structure so still learning. – jsLearner Feb 08 '19 at 15:22
  • thanks @trincot for your inputs, i will edit my answer after referring to related link. – user1579234 Feb 08 '19 at 15:24
  • @jsLearner: you are right, the complexity of this solution is: `n2` and not a preferred solution. I wanted to share a solution closer to how you are trying to solve. Preferred solution should be one of the many solutions that @trincot shared. They need less code and have better performance. – user1579234 Feb 08 '19 at 15:29
0

as a javascript dev you should be comfortable wit functional programming & higher-order functions so check the doc to get more understanding of some useful functions: like filter - find - reduce - findIndex map ...

Documentation

Now to answer your question:

at first you should think by step :

  • Get the occurrence of an item in an array as function:

const arr = [2, 5, 6, 2, 4, 5, 6, 8, 2, 5, 2]

const res = arr.reduce((numberofOcc, item) => {
  if (item === 2)
    numberofOcc++

    return numberofOcc
}, 0);

console.log(`result without function ${res}`);

/* so my function will be */


const occurenceFun = (num, arr) => {
  return arr.reduce((numberofOcc, item) => {
    if (item === num)
      numberofOcc++

      return numberofOcc
  }, 0);

}

console.log(`result using my function ${occurenceFun(2, arr)}`);
  • Now i have this function so i can use it inside another function to get the higher occurrence i have in an array

const arr = [1, 2, 5, 6, 8, 7, 2, 2, 2, 10, 10, 2]

const occurenceFun = (num, arr) => {
  return arr.reduce((numberofOcc, item) => {
    if (item === num)
      numberofOcc++

      return numberofOcc
  }, 0);

}



/*let's create our function*/

const maxOccurenceFun = arr => {
  let max = 0;

  arr.forEach(el => {
    if (max < occurenceFun(el, arr)) {
      max = el
    }
  })

  return max;

}

console.log(`the max occurence in this array is : ${maxOccurenceFun(arr)}`);
Aziz.G
  • 3,599
  • 2
  • 17
  • 35