[leetcode 268] Missing Number

268. Missing Number

https://leetcode.com/problems/missing-number/

해결 과정

입력 IntArray nums를 돌면서, 등장하는 숫자를 idx로 보아 checkArr 의 idx 번째 값을 true로 변경한다. checkArr 를 돌면서, false인 값을 만나면 return idx 한다.

코드

fun missingNumber(nums: IntArray): Int {
  var checkArr = BooleanArray(nums.size+1){false}
  
  nums.forEach { num ->
    checkArr[num] = true
  }
        
  checkArr.forEachIndexed { idx, check ->
    if(!check) {
      return idx
    }
  }
  return -1
}   

배운 점

• 위의 방법대로 문제를 풀면, Accept는 되지만 문제의 요건 사항인 space complexity O(1)를 만족시키지 못한다. 고민하다가, 솔루션을 보니 간단하지만 재미있는 해결방법이 있었다.

누락된 숫자는 가우스의 덧셈에 따라 예상한 값에서 실제 값을 빼기만 하면 되는 것이다.