625. Minimum Factorization

LeetCode medium original: C# #array #bit-manipulation #csharp #leetcode #medium

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

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

Example:

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
}

Algorithm

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

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

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

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.