/* Алгоритмы-числа Число S состоит из M чисел, например, S=370 и M(количество цифр)=3 Реализовать логику метода getNumbers, который должен среди натуральных чисел меньше N (long) находить все числа, удовлетворяющие следующему критерию: число S равно сумме его цифр, возведенных в M степень getNumbers должен возвращать все такие числа в порядке возрастания

Пример искомого числа: 370 = 333 + 777 + 000 8208 = 8888 + 2222 + 0000 + 8888

На выполнение дается 10 секунд и 50 МБ памяти. */

package com.javarush.test.level20.lesson10.bonus01;

import java.util.*;

public class Solution
{
    private static Set<Integer> treeSet = new TreeSet<>(new Comparator<Integer>()
    {
        @Override
        public int compare(Integer o1, Integer o2)
        {
            if (o1 > o2) return 1;
            else if (o1 < o2) return -1;
            else return 0;
        }
    });

    public static void main(String[] args)
    {
        Date start = new Date();
        long startTime = start.getTime();

        int[] result = getNumbers(2000000000);

        Date finish = new Date();
        long finishTime = finish.getTime();

        System.out.println(Arrays.toString(result));
        double executionTime = (double) (finishTime - startTime) / 1000;
        double requiredMemory = (double) (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / 1048576;
        System.out.println(String.format("Execution Time : %.3f seconds;\nRequired Memory : %.3f MegaBytes.", executionTime, requiredMemory));
    }

    public static int[] getNumbers(int N)
    {
        for (Integer i = 1; i < N; )    // N?
        {
            if (isNumberUnique(i))
            {
                int sumOfPowers = sum(i);
                if (isArmstrongNumber(sumOfPowers))
                {
                    treeSet.add(sumOfPowers);
                }
                i++;
            } else
            {
                String sNum = i.toString();
                if (!sNum.contains("0"))
                    if (sNum.charAt(0) >= sNum.charAt(sNum.length() - 1))
                    {
                        StringBuilder stringBuilder = new StringBuilder(sNum);
                        int index = 1;
                        for (int j = 1; j < stringBuilder.length(); j++)
                        {
                            if (stringBuilder.charAt(j) < stringBuilder.charAt(index))
                            {
                                index = j;
                            }
                        }
                        stringBuilder.setCharAt(index, sNum.charAt(sNum.length() - 1));
                        for (int j = index + 1; j < stringBuilder.length(); j++)
                            stringBuilder.setCharAt(j, '0');
                        sNum = stringBuilder.toString();
                        i = Integer.parseInt(sNum);
                    } else
                        i = Integer.parseInt(sNum.substring(sNum.length() - 1)) * (int) Math.pow(10, sNum.length() - 1);
                else
                {
                    StringBuilder stringBuilder = new StringBuilder(sNum);
                    stringBuilder.setCharAt(sNum.indexOf("0"), sNum.charAt(sNum.length() - 1));
                    stringBuilder.setCharAt(sNum.length() - 1, '0');
                    sNum = stringBuilder.toString();
                    i = Integer.parseInt(sNum);
                }
            }
        }

        int[] result = new int[treeSet.size()];
        int i = 0;
        for (int num : treeSet)
        {
            result[i++] = num;
        }

        return result;
    }

    private static boolean isArmstrongNumber(int number)
    {
        if (sum(number) == number)
        {
            return true;
        }

        return false;
    }

    private static boolean isNumberUnique(int number)
    {
        int lastDigit = 0;
        int currentDigit;

        while (number > 0)
        {
            currentDigit = number % 10;
            if (lastDigit > currentDigit)
            {
                return false;
            }
            lastDigit = currentDigit;
            number /= 10;
        }

        return true;
    }

    public static int sum(int a)
    {
        int addition = 0;
        int d = ("" + a).length();
        int b = a % 10;
        while (a >= 1)
        {
            addition += Math.pow(b, d);
            a /= 10;
            b = a % 10;
        }

        return addition;
    }
}

Вывод:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315, 24678050, 24678051, 88593477, 146511208, 472335975, 534494836, 912985153] Execution Time : 0,379 seconds; Required Memory : 20,151 MegaBytes.

Подскажите, пожалуйста, почему программа не проходит тестирование? Убирать метод main пробовал, цикл до N включительно тоже.

задан 27 Июл '16, 08:19

ivladik's gravatar image

ivladik
112
одобрено: 0%

закрыто 13 Сен, 16:47

AndyRad's gravatar image

AndyRad
13.1k29

Вопрос был закрыт по следующей причине: "Problem is not reproducible or outdated" AndyRad 13 Сен, 16:47


Реализовал метод getNumbers без строк, всё - равно не работает.

package com.javarush.test.level20.lesson10.bonus01;

import java.util.*;

public class Solution
{
    private static Set<Integer> treeSet = new TreeSet<>(new Comparator<Integer>()
    {
        @Override
        public int compare(Integer o1, Integer o2)
        {
            if (o1 > o2) return 1;
            else if (o1 < o2) return -1;
            else return 0;
        }
    });
    private static List<Integer> mas1 = new ArrayList<>();
    private static List<Integer> mas2 = new ArrayList<>();

    public static void main(String[] args)
    {
        Date start = new Date();
        long startTime = start.getTime();

        int[] result = getNumbers(2000000000);

        Date finish = new Date();
        long finishTime = finish.getTime();

        System.out.println(Arrays.toString(result));
        double executionTime = (double) (finishTime - startTime) / 1000;
        double requiredMemory = (double) (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / 1048576;
        System.out.println(String.format("Execution Time : %.3f seconds;\nRequired Memory : %.3f MegaBytes.", executionTime, requiredMemory));
    }

    public static int[] getNumbers(int N)
    {
        for (int i = 1; i < N; ) // N?  ArrayList?
        {
            if (isNumberUnique(i))
            {
                int sumOfPowers = sum(i);
                if (isArmstrongNumber(sumOfPowers))
                {
                    treeSet.add(sumOfPowers);
                }
                i++;
            } else
            {
                int number = i;
                while (number > 0)
                {
                    int tmp = number % 10;
                    mas1.add(tmp);
                    number /= 10;
                }
                for (int j = mas1.size() - 1; j >= 0; j--)
                    mas2.add(mas1.get(j));
                mas1.clear();
                if (!mas2.contains(0))
                    if (mas2.get(0) >= mas2.get(mas2.size() - 1))
                    {
                        int indexOfMin = 1;
                        for (int j = 1; j < mas2.size(); j++)
                        {
                            if (mas2.get(j) < mas2.get(indexOfMin))
                            {
                                indexOfMin = j;
                            }
                        }
                        mas2.set(indexOfMin, mas2.get(mas2.size() - 1));
                        for (int j = indexOfMin + 1; j < mas2.size(); j++)
                            mas2.set(j, 0);
                        number = 0;
                        while (mas2.size() != 0)
                        {
                            number += (mas2.get(0) * (int) Math.pow(10, mas2.size() - 1));
                            mas2.remove(0);
                        }
                        i = number;
                    } else
                    {
                        i = (mas2.get(mas2.size() - 1)) * (int) Math.pow(10, mas2.size() - 1);
                        mas2.clear();
                    }
                else
                {
                    mas2.set(mas2.indexOf(0), mas2.get(mas2.size() - 1));
                    mas2.set(mas2.size() - 1, 0);
                    while (mas2.size() != 0)
                    {
                        number += (mas2.get(0) * (int) Math.pow(10, mas2.size() - 1));
                        mas2.remove(0);
                    }
                    i = number;
                }
            }
        }

        int[] result = new int[treeSet.size()];
        int i = 0;
        for (int num : treeSet)
        {
            result[i++] = num;
        }

        return result;
    }

    private static boolean isArmstrongNumber(int number)
    {
        if (sum(number) == number)
        {
            return true;
        }

        return false;
    }

    private static boolean isNumberUnique(int number)
    {
        int lastDigit = 0;
        int currentDigit;

        while (number > 0)
        {
            currentDigit = number % 10;
            if (lastDigit > currentDigit)
            {
                return false;
            }
            lastDigit = currentDigit;
            number /= 10;
        }

        return true;
    }

    public static int sum(int a)
    {
        int addition = 0;
        int d = ("" + a).length();
        int b = a % 10;
        while (a >= 1)
        {
            addition += Math.pow(b, d);
            a /= 10;
            b = a % 10;
        }

        return addition;
    }
}

Вывод:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315, 24678050, 24678051, 88593477, 146511208, 472335975, 534494836, 912985153] Execution Time : 0,480 seconds; Required Memory : 8,641 MegaBytes.

ссылка

опубликован 27 Июл '16, 19:16

ivladik's gravatar image

ivladik
112
одобрено: 0%

Изменил метод sum, избавившись от строки. Не прошло.

public static int sum(int a)
    {
        int addition = 0;
        int len = 0;
        int tmp = a;
        while (tmp > 0)
        {
            len++;
            tmp /= 10;
        }
        //int d = ("" + a).length();
        int b = a % 10;
        while (a >= 1)
        {
            addition += Math.pow(b, len);
            a /= 10;
            b = a % 10;
        }

        return addition;
    }
ссылка

опубликован 27 Июл '16, 19:29

ivladik's gravatar image

ivladik
112
одобрено: 0%

Свою задачу сделал со второй попытки, из-за того, что не знал, что "0" - не натуральное число... Все состоит из мелочей.

ссылка

опубликован 12 Ноя '16, 15:30

Kirilo's gravatar image

Kirilo
29918
одобрено: 22%

Следить за вопросом

По Email:

После авторизации вы сможете подписаться на любые обновления здесь

Основы Markdown

  • *italic* or _italic_
  • **bold** or __bold__
  • ссылка:[текст](http://url.com/ "заголовок")
  • изображение?![alt текст](/path/img.jpg "заголовок")
  • нумерованный список: 1. Foo 2. Bar
  • Для того чтобы добавить разрыв строки просто добавьте два пробела.
  • основные HTML тэги, также поддерживаются

Тэги:

×3,808
×4

Задан: 27 Июл '16, 08:19

Просмотров: 361 раз

Отредактирован: 13 Сен, 16:47