LeetCode 2521. Distinct Prime Factors of Product of Array

LeetCode Notes [54]: Kotlin || Easy to understand

渚園ソフトボール場

Problem

Distinct Prime Factors of Product of Array - LeetCode

Intuition

Find all prime numbers in the range of 2to maximum number of the nums array, if any of the prime number is a factor of num, increment the count by 1.

Implementation

class Solution {
    fun distinctPrimeFactors(nums: IntArray): Int {
        var max = Int.MIN_VALUE
        nums.forEach {
            if (it > max) {
                max = it
            }
        }

        var count = 0
        for (prime in 2..max) {
            var isPrime = true
            for (j in 2 until prime) {
                if (prime % j == 0) {
                    isPrime = false
                    break
                }
            }
            if (isPrime) {
                run loop@{
                    nums.forEach { num ->
                        if (num % prime == 0) {
                            count++
                            return@loop
                        }
                    }
                }
            }
        }

        return count
    }
}

Complexity Analysis

• Time Complexity: O(maxNumber*(maxNumber + nums.length))
• Space Complexity: O(1)

Similar Questions

LeetCode 650. 2 Keys Keyboard