Python - Algorithm #35

Python Algorithm

LeetCode

1287. Element Appearing More Than 25% In Sorted Array

• Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time, return that integer.
• Constraints
  • 1 ≤ arr.length ≤ 10⁴
  • 0 ≤ arr[i] ≤ 10⁵

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        quater = len(arr) / 4
        c = Counter(arr)
        for num, cnt in c.items():
            # cnt를 quater와 비교
            # 만약 quater보다 크다면 answer로 지정
            if cnt > quater:
                answer = num
        return answer

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        answer = 0
        d = defaultdict(int)
        for num in arr:
            d[num] += 1
        standard = len(arr) / 4
        for num, cnt in d.items():
            if cnt > standard:
                answer = num
                break
        return answer

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        for n in arr:
            if arr.count(n) > len(arr) * 0.25:
                return n
        return 0

from collections import Counter

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        c = Counter(arr)
        for key, value in c.items():
            if value > len(arr) * 0.25:
                return key

---

263. Ugly Number

• An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
• Given an integer n, return true if n is an ugly number.
• Constraints
  • -2³¹ ≤ n ≤ 2³¹ - 1

class Solution:
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False
        # while 문을 사용해서 n을 1로 만들 때까지
        # 2, 3, 5로 나눠주기
        # 만약 나눠지지 않는다면 return False
        factors = [2, 3, 5]
        while True:
            if n == 1:
                break
            flag = False
            # 2, 3, 5로 나누어지는지 체크
            # 하나라도 나누어지는 수가 없으면 return False
            # 나누어지면 해당 수로 n 나눠주기
            for factor in factors:
                if n % factor == 0:
                    flag = True
                    n /= factor
                    break
            return flag
        return True

class Solution:
    def isUgly(self, n: int) -> bool:
        if n == 0:
            return False
        for i in [2, 3, 5]:
            while n % i == 0:
                n /= i
            if n == 1:
                return True

class Solution:
    def isUgly(self, n: int) -> bool:
        while True:
            if n == 0:
                return False
            if n == 1:
                return True
            elif n % 2 == 0:
                n /= 2
            elif n % 3 == 0:
                n /= 3
            elif n % 5 == 0:
                n /= 5
            else:
                return False

---

https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/

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