625. Minimum Factorization

leetcode medium

#array#bit-manipulation#csharp#leetcode#medium

Task

Если задано целое положительное число num, верните наименьшее целое положительное число x, умножение каждого разряда которого равно num. Если ответа нет или ответ не помещается в 32-битное знаковое целое число, возвращается 0.

Пример:

Input: num = 48

Output: 68

C# solution

matched/original

public class Solution {
    public int SmallestFactorization(int num) {
        if (num == 1) return 1;
        
        List<int> factors = new List<int>();
        
        for (int i = 9; i >= 2; i--) {
            while (num % i == 0) {
                factors.Add(i);
                num /= i;
            }
        }
        
        if (num > 1) return 0;
        
        long result = 0;
        for (int i = factors.Count - 1; i >= 0; i--) {
            result = result * 10 + factors[i];
            if (result > int.MaxValue) return 0;
        }
        
        return (int) result;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int SmallestFactorization(int num) {
        if (num == 1) return 1;
        
        List<int> factors = new List<int>();
        
        for (int i = 9; i >= 2; i--) {
            while (num % i == 0) {
                factors.push_back(i);
                num /= i;
            }
        }
        
        if (num > 1) return 0;
        
        long result = 0;
        for (int i = factors.size() - 1; i >= 0; i--) {
            result = result * 10 + factors[i];
            if (result > int.MaxValue) return 0;
        }
        
        return (int) result;
    }
}

Java solution

matched/original

public class Solution {
    public int smallestFactorization(int num) {
        if (num == 1) return 1;
        
        List<Integer> factors = new ArrayList<>();
        
        for (int i = 9; i >= 2; i--) {
            while (num % i == 0) {
                factors.add(i);
                num /= i;
            }
        }
        
        if (num > 1) return 0;
        
        long result = 0;
        for (int i = factors.size() - 1; i >= 0; i--) {
            result = result * 10 + factors.get(i);
            if (result > Integer.MAX_VALUE) return 0;
        }
        
        return (int) result;
    }
}

JavaScript solution

matched/original

function smallestFactorization(num) {
    if (num === 1) return 1;
    
    const factors = [];
    
    for (let i = 9; i >= 2; i--) {
        while (num % i === 0) {
            factors.push(i);
            num /= i;
        }
    }
    
    if (num > 1) return 0;
    
    let result = 0;
    for (let i = factors.length - 1; i >= 0; i--) {
        result = result * 10 + factors[i];
        if (result > 2**31 - 1) return 0;
    }
    
    return result;
}

Python solution

matched/original

def smallestFactorization(num):
    if num == 1:
        return 1
    
    factors = []
    
    for i in range(9, 1, -1):
        while num % i == 0:
            factors.append(i)
            num //= i
    
    if num > 1:
        return 0
    
    result = 0
    for factor in reversed(factors):
        result = result * 10 + factor
        if result > 2**31 - 1:
            return 0
    
    return result

Go solution

matched/original

package main

import "math"

func smallestFactorization(num int) int {
    if num == 1 {
        return 1
    }
    
    factors := []int{}
    
    for i := 9; i >= 2; i-- {
        for num % i == 0 {
            factors = append(factors, i)
            num /= i
        }
    }
    
    if num > 1 {
        return 0
    }
    
    result := 0
    for i := len(factors) - 1; i >= 0; i-- {
        result = result * 10 + factors[i]
        if result > math.MaxInt32 {
            return 0
        }
    }
    
    return result
}

Explanation

Algorithm

Если num равно 1, верните 1. Инициализируйте массив для хранения множителей.

Разделите num на множители от 9 до 2, пока num больше 1. Если в процессе остаются множители больше 9, верните 0.

Постройте результат, собирая найденные множители в обратном порядке. Если результат больше 32-битного целого числа, верните 0.

😎