137. Single Number II

Stanislav Gumeniuk included in leetcode leetcode-problem

2020.06.22 92 words One minute

Contents

Problem

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

example

1
2


Input: [2,2,3,2]
Output: 3

1
2


Input: [0,1,0,1,0,1,99]
Output: 99

Solution

Sort array and walk

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func singleNumber(nums []int) int {
    sort.Ints(nums)
    
    for idx:=0; idx<len(nums); idx+=3 {
        if idx<len(nums)-3 && nums[idx]!=nums[idx+2] {
            return nums[idx]
        }
    }
    
    return nums[len(nums)-1]
}