[코딩 테스트 문제 + 풀이] Time Complexity

Q. Return the smallest positive interger (greater than 0) that does not occur in A. 

     e.g.  A = [1, 3, 6, 4, 1, 2]    // SHOULD return 5

 

    Given A = [1, 2, 3]   // SHOULD return 4

    Given A = [-1, -2]   // SHOULD return 1

 

function solution(A) {
  for (i=1; i <1000000; i++) {
    if(!A.includes(i)) return i;
  }
}

 

 

 

 

 

Q. 1, 2, 3, 4, 5, 7, 8... missing element 찾기   // SHOULD return 6

 

function solution(A) {
  let actualSum = 0;
  A.forEach(number => actualSum += number);

  let maxNumber = A.length + 1;
  let expectedSum = (maxNumber * (maxNumber + 1) /2);
  
  return expectedSum - actualSum;
}

 

 

 

 

 

Q. Equilibrium (평행 조건)

 

function solution(A) {
  let leftSum = A[0];
  let rightSum = 0;
  A.slice(1).forEach(callbackfn: number => rightSum += number);

  let diff = Math.abs(x:leftSum - rightSum);
  for (let i = 1; i < A.length - 1; i++) {
    leftSum += A[i];
    rightSum -= A[i];
    let currentDiff = Math.abs(x:leftSum - rightSum);
    if (diff > currentDiff) diff = currentDiff;
  }
  return diff;
}

console.log(solution(A:[3, 1, 2, 4, 3]));     //1