package main

func majorityElementOld(nums []int) int {
	m := map[int]int{}
	n := int(len(nums) / 2)
	for _, v := range nums {
		m[v]++
		if m[v] > n {
			return v
		}
	}
	return 0
}

// ~ little trick
func majorityElement(nums []int) int {
	var cnt = 0
	var num int
	for _, v := range nums {
		if cnt == 0 {
			num = v
		}
		if v == num {
			cnt++
		} else {
			cnt--
		}
	}
	return num
}

// func main() {
// 	arr := []int{1, 1, 3}
// 	fmt.Println(majorityElement(arr))
// }