Is this task really asking us to return every possible armstrong number that could be entered?

Question about the task

Under discussion

it grabs the correct Armstrong numbers when you run it, but times out on verification. [1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407] memory 512 time = 0 [1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834] memory 19184 time = 0

Suppose the number S consists of M digits. For example, if S = 370, then M (the number of digits) = 3
Implement the getNumbers method. Among natural numbers less than N (long),
it should find all the numbers satisfying the following criterion:
The number S is equal to the sum of its digits raised in the Mth power
getNumbers should return all such numbers in ascending order.

Examples of such numbers:
370 = 3*3*3 + 7*7*7 + 0*0*0 8208 = 8*8*8*8 + 2*2*2*2 + 0*0*0*0 + 8*8*8*8

The search is allowed to take 10 seconds and use 50 MB of memory.
The main method is not tested.

Requirements:

A public static long[] getNumbers(long N) method must be created in the Solution class.
The getNumbers method should not throw exceptions for any input.
All returned numbers must be strictly less than N.
The getNumbers method must return the array of numbers that satisfy the task conditions.

package com.codegym.task.task20.task2025; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; /* Number algorithms */ public class Solution { public static long[] getNumbers(long N) { List<Long> longsList = new ArrayList<>(); for (long i = N; i > 0; i--) { long S = 0; String strNum = Long.toString(i); int M = strNum.length(); String[] longArray = strNum.split("(?<=\\d)"); for (String x : longArray) { S += (long) Math.pow(Double.parseDouble(x), M); } if (S == i) { longsList.add(S); } } Collections.sort(longsList); return longsList.stream().mapToLong(Long::longValue).toArray(); } public static void main(String[] args) { long a = System.currentTimeMillis(); System.out.println(Arrays.toString(getNumbers(1000))); long b = System.currentTimeMillis(); System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024)); System.out.println("time = " + (b - a) / 1000); a = System.currentTimeMillis(); System.out.println(Arrays.toString(getNumbers(1000000))); b = System.currentTimeMillis(); System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024)); System.out.println("time = " + (b - a) / 1000); } }

Comments (7)

Popular
New
Old

You must be signed in to leave a comment

Jaime Padilla

Level 41 , Chandler, United States

Expert

21 January 2023, 00:55

Always so detailed Guadalupe! I will be saving your advice in my notes again. Thank you for everything you do! Btw, when are you going to hit level 41? I feel that you are light years ahead of this course now.

Guadalupe Gagnon

Level 37 , Tampa, United States

12 January 2023, 17:36

When I try your code with the number 10,000,000 it took 9 seconds to complete. A long can hold values up to 9,223,372,036,854,775,807. This code wouldn't be able to find the correct answer fast enough (just doubling to 20,000,000 took 18 seconds to finish). Personally I don't think this is a beginner task because it requires a level of optimization that is quite a bit above beginner, but I can leave some tips for optimization: #1 working with Strings is very slow. You should immediately convert to a number and only use numbers when doing math. #2 line 21: you get a new value of M for every single number, however the numbers 1-9 M will be 1 - the numbers 10-99 M will be 2 - the number 100-999 M will be 3. That means you need to change the value of M only three times for the numbers 1-999 instead of nine hundred and ninety nine times. If you went to the max of a long you would only need to change N 25 times. #3 lines 23-25: every time M changes there are only 10 possible outcomes for line 24. For example, if you had a number that was 4 digits long the 10 possible outcomes (actually 8 because the digit 0 is still 0 and 1 is still 1 no matter what M is) for line 24 would be: 0: 0 1: 1 2: 16 3: 81 4: 256 5: 625 6: 1296 7: 2401 8: 4096 9: 6561 Right now your code gets each number, breaks it into each digit, and uses Math.pow() on each of those. By just saving the results of Math.pow(x, M) (where x is the each number 0-9) then recalling the saved value for each digit saves a TON of time. I will include some example code to break this down.

Guadalupe Gagnon

Level 37 , Tampa, United States

12 January 2023, 17:38

public static void main(String[] args) {
   long temp = 0; // just to use to set a value
   long startNumber = 1000000, max = startNumber * 10;
   double M = Long.toString(startNumber).length();

   System.out.println("Original algorithm");
   long BeginTime = System.currentTimeMillis();
   for(long i = startNumber; i < max; i++){
      long S = 0;
      String strNum = Long.toString(i);
      int m = strNum.length();
      String[] longArray = strNum.split("(?<=\\d)");
      for (String x : longArray)
         temp = (long) Math.pow(Double.parseDouble(x), m);

   }
   System.out.println("Time taken with original algorithm - " + (System.currentTimeMillis() - BeginTime) + "ms");

   System.out.println();
   System.out.println("Working with a number instead of Strings, and using M calculated 1 time");
   BeginTime = System.currentTimeMillis();
   for(long i = startNumber; i < max; i++){
      long digits = i;

      while(digits > 0) {
         temp = (long) Math.pow((double) digits % 10, M);
         digits /= 10;
      }
   }
   System.out.println("Time taken to use Math.pow() - " + (System.currentTimeMillis() - BeginTime) + "ms");

   System.out.println();
   System.out.println("Now using Hashed values");
   BeginTime = System.currentTimeMillis();
   long[] values = new long[10];

   for(int i = 0; i < 10; i++) values[i] = (long)Math.pow((double)i, M);

   System.out.println(Arrays.toString(values));
   for(long i = startNumber; i < max; i++){
      long digits = i;

      while(digits > 0) {
         temp = values[(int)(digits % 10)];
         digits /= 10;
      }
   }
   System.out.println("Time taken using hashed values - " + (System.currentTimeMillis() - BeginTime) + "ms");
}

Guadalupe Gagnon

Level 37 , Tampa, United States

12 January 2023, 17:47

This code is basically the algorithm needed for this task without the actual checking for the required number. It takes 3 different approached and times them to output and compare the results. Line 3: you can change the value of startNumber to be whatever positive multiple of 10 you want (eg, 1, 10, 100, 1000 etc) to see different results Lines 7-16: This is your abrreviated aglorithm that turns each number to a String, gets a value for M, gets each digit, converts back to a number, does Math.pow(digit, m). Lines 22-29: This algorithm works the same but doesn't use Strings, and also doesn't get a new value of M for each new number. Lines 40-47: And finally this uses all the tips that I gave. The results when I run this code are: Original algorithm Time taken with original algorithm - 7832ms Working with a number instead of Strings Time taken to use Math.pow() - 3032ms Now using Hashed values [0, 1, 128, 2187, 16384, 78125, 279936, 823543, 2097152, 4782969] Time taken using hashed values - 94ms By not using Strings it doubles the speed of your algorithm. Hashing values instead of calling Math.pow() on every single digit makes it roughly 83 times faster.

Jaime Padilla

Level 41 , Chandler, United States

Expert

22 January 2023, 01:14

I know it probably doesn't seem like much to you, but this seems really advanced to me. I feel that you have to be pretty well-versed in mathematics to be able to think of an algorithm as you have.

Guadalupe Gagnon

Level 37 , Tampa, United States

23 January 2023, 14:16

This is one of the 2 or 3 tasks that I actually was so frustrated with that I just googled the answer. Like I said, I don't think this task is fair for beginners. Codegym needs to really lighten up on the grading and accept answers that are correct, however unoptimized they are. Personally I spent about 2 years (after passing the task with google) coming back and updating my code with new ideas and techniques that I had picked up. I shared a bunch of really great videos on a codegym forum post (link here). Most of them are about algorithms. Go watch the two videos that I shared about radix sort. Radix sorting is one of the fastest methods of sorting very large sets of unsorted numbers. Those two really blew my mind on how easy the actual algorithm is to understand.

Jaime Padilla

Level 41 , Chandler, United States

Expert

24 January 2023, 04:13

I'll definitely check it out. Thank you again. Also, just saved it in my personal notes. You are a great teacher.