Answer for task 137

Task137.java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

public class Task137 {
	public static void main(String[] args) {
		System.out.println("1		= " + solve(1));		// 1
		System.out.println("2		= " + solve(2));		// 2
		System.out.println("10		= " + solve(10));		// 25
		System.out.println("11		= " + solve(11));		// -1
		System.out.println("12		= " + solve(12));		// 26
		System.out.println("13		= " + solve(13));		// -1
		System.out.println("14		= " + solve(14));		// 27
		System.out.println("15		= " + solve(15));		// 35
		System.out.println("16		= " + solve(16));		// 28
		System.out.println("34		= " + solve(34));		// -1
		System.out.println("100		= " + solve(100));		// 455
		System.out.println("168		= " + solve(168));		// 378
		System.out.println("216		= " + solve(216));		// 389
		System.out.println("324		= " + solve(324));		// 499
		System.out.println("330		= " + solve(330));		// -1
		System.out.println("432		= " + solve(432));		// 689
		System.out.println("648		= " + solve(648));		// 899
		System.out.println("1000	= " + solve(1000));		// 5558
		System.out.println("2520	= " + solve(2520));		// 5789
		System.out.println("4212	= " + solve(4212));		// -1
		System.out.println("7350	= " + solve(7350));		// 55677
		System.out.println("21600	= " + solve(21600));	// 255689
		System.out.println("30240	= " + solve(30240));	// 256789
		System.out.println("1000000	= " + solve(1000000));	// 55555588
		System.out.println("1000000000	= " + solve(1_000_000_000));	// 555555555888
		System.out.println("387420489	= " + solve(387420489));	// 999999999
	}

	private static long solve(int n) {
		if (n < 10) {
			return n;
		}
		/*
		Идея заключается в том, что необходимо разложить данное число N так,
		чтобы все его сомножители были меньше 9 (т.е. произвести факторизацию числа так, чтобы
		все сомножители были <= 9) ( ну и очевидно, больше 2)
		Иначе может получится ситуация, если сомножитель будет больше чем 9 (т.е. число вида ab) и тогда,
		мы можем предположить, что результат у нас должен быть в виде q*w*e*...*ab.
		Но это не сработает, т.к. мы должы по условию делать q*w*e*...*a*b.

		Логично, что для простых чисел мы всегда вернем -1.

		Соответственно, если мы в какой то момент времени видим, что числе не делится на число
		из диапазона 2-9, значит выводим -1. Иначе запоминаем все цифры и выводим их в порядке возрастания.

		Начнем делить мы с 9 до 2, т.к. у нас может возникнуть ситуация ( если мы будем делить с 2 по 9), например, с числом 100
		что мы поделим 100 /2 = 50, и потом 50/2 = 25. Значит у нас будет уже цифры 2 и 2, хотя если бы мы делили в обратном порядке,
		то мы сразу бы дошли до 5 ( 100 / 5 = 20), потом снова до 5 ( 20 / 5 = 4) и уже полчили 4 => ответ 455
		 */

		List<Integer> list = new ArrayList<>();

		while (n >= 10) {
			boolean found = false;

			for (int i = 9; i >= 2; i--) {
				if (n % i == 0) {
					// тут у нас i - целое число <= 9.
					// запоминаем это число, делим исходное на i
					// и повторяем операцию

					list.add(i);
					n = n / i;

					found = true;
					break;
				}
			}

			if (!found) { // наше число N не делится ни на одно из чисел в диапазоне 9-2 => возвращаем -1
				return -1;
			}
		}

		list.add(n);
		list.sort(Comparator.naturalOrder());

		return Long.valueOf(list.stream().map(Object::toString).collect(Collectors.joining("")));
	}
}