Задача по поиску количества палиндромов, которые можно представить в виде суммы квадратов последовательных чисел

Question

Здраствуйте, я месяц уже изучаю Java и частенько решаю задачи на таком сайте как CodeWars. И вот во время решения очередного задания, произошла ошибка. P.S: если в друг вам будет не понятно то что я объяснил, перейдите по ссылке и посмотрите задание сами: задание на поиск палиндромов, возможно попробуйте решите его и подскажите мне что я не так сделал. Ибо мой алгоритм то возвращает значение на 1 больше то меньше. Ну или предложите свою реализацию

Дело в том что тесты проходят успешно. Но во время попытки опубликовать свое решение рандомные тесты дают ошибку. Суть задания в том что-бы посчитать количество чисел палиндромов (это то что задом наперед означет тоже самое). Например: 151, 99. Как их не крути с одно и другой стороны они читаются как 99, и 151. Ну или на примере слова, например: ДОВОД. С какой стороны не прочти оно все равно ДОВОД.).

Условие: Так вот на вход вы получаете какоето значение например 1000 (в коде это n) и нужно вернуть количество чисел палиндромов которые получаются в результате сложения последовательных чисел в квадрате и в итоге результат сложения должен быть меньше чем 1000 (Тоесть, то n которое мы изначально знаем).

Например: 1^2 + 2^2 = 5. Или так: 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2 = 595. От сюда мы видем что число 595 действительно палиндром. Который был создан из суммы последовательных квадратов. Однозначные тоже считаются палиндромами так как созданы из последовательности суммы квадратов.

Посмотрите мой код: (Помогите понять что не так в нем работает):

public static int values (int n){
    //..
  int countElement = 0;
    // Суть первого цикла в том что-бы по очереди брать значения начинающиеся с 1, а второй добавляет к этому значению последовательность. Получается что-то типа: 1^2 + 2^2...
    for(int i = 1; isTwoPowResult(i, n); i++) { 
      
      int sum = (int) Math.pow(i, 2); 
      
      for(int j = i + 1; ; j++) {
        
        sum += (int) Math.pow(j, 2);
        
        if(sum >= n) { 
          break;
        }
        
        StringBuilder builder = new StringBuilder(Integer.toString(sum));
        
        if(new String(builder).equals(new String(builder.reverse()))) { 
           countElement++;
        }           
       } 
      }
   return countElement;
}

public static boolean isTwoPowResult(int index, int n) { 
   return ((int) Math.pow(index, 2) + ((int) Math.pow(++index, 2))) <=  n;
}

Answer 1

Проблема в том, что две разные последовательности чисел могут давать одинаковую сумму квадратов чисел.

Например: сумма квадратов от 9 до 118 равна 554455, но сумма квадратов от 331 до 335 также равна 554455. Соответственно, это число в Вашем решении будет посчитано дважды.

Чтобы исправить, нужно в методе считать только уникальные значения sum. Для этого можно завести множество возможных сумм:

Set<Integer> valueSet = new HashSet<>();

Добавлять в него все полученные значения:

 valueSet.add(sum);

И возвращать количество найденных уникальных сумм, т.е. размер множества:

 return valueSet.size();

Без переменной countElement можно обойтись.

Я внес эти изменения и задача прошла на codewars.

P.S. В любом случае предложил бы возводить числа в квадрат через простое перемножение x*x, а не через (int) Math.pow(x, 2). Функция Math.pow работает с вещественными числами, и соответственно, может давать результаты с погрешностью . Здесь это вроде как не влияет на результат, но в дальнейшем погрешность может подвести.

БЛОГ НА HUSL

Задача по поиску количества палиндромов, которые можно представить в виде суммы квадратов последовательных чисел

Ответы (1 шт):