It seems that everything is fine, but I guess I am missing something.

Question about the task

Resolved

I get great timing and decent memory usage in IntelliJ Idea. The results also seem to be correct. Do I miss something? Is there are corner case I am missing out? Thanks!

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.List; import java.util.ResourceBundle; /* Number algorithms */ public class Solution { public static void main(String[] args) { long a = System.currentTimeMillis(); System.out.println(Arrays.toString(getNumbers(54748))); 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(100000000))); b = System.currentTimeMillis(); Runtime t = Runtime.getRuntime(); System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024)); System.out.println("time = " + (b - a) / 1000); } public static int calculatePows(int length, int piece){ int result = piece; for (int i = 1; i <length ; i++) { result *= piece; } return result; } public static long[] getNumbers(long N) { if (N <= 0) return new long[0]; List<Integer> resultList = new ArrayList<>(); for (int i = 1; i <N ; i++) { ResourceBundle.clearCache(); String currentNum = String.valueOf(i); int S = 0; for (int j = 0; j <currentNum.length() ; j++) { int piece = (currentNum.charAt(j) - '0'); S += calculatePows(currentNum.length(), piece); } if (S == i) { resultList.add(S); } } long[] result = new long[resultList.size()]; for (int i = 0; i <resultList.size(); i++) { result[i] = resultList.get(i); } return result; } }

Comments (3)

Popular
New
Old

You must be signed in to leave a comment

Guadalupe Gagnon

Level 37 , Tampa, United States

18 November 2020, 15:23

solution

Some things: #1 The correct answer should include numbers less than the max value of a long, which is "9223372036854775807", The method used to calculate each power returns an in, which has the max value of "2147483647". This means that any numbers that meet the requirements that are between 2147483648 and 9223372036854775807 will be impossible to find with this program. When I pass in anything larger than an int a blank array is returned. #1a Also your for loops are using ints for the counter. Wouldn't work for a max in the long value. #2 Strings are not a good solve when working with numbers. They take up quite a bit of space in the computers memory. For example, a long of any value will take up 8 bytes of memory, where figuring out the memory a string takes up involves multiplying the length by 2, adding 38, then rounding up to the nearest multiple of 8. Turning the max int into a string would take up ~64 bytes. That costs 8x more memory than just working with a long. String Memory Reading Here is some code to help:

long i = 1;
long mul10 = 10; // upper bound will be multiple of 10: 10, 100, 1000, 10000 etc
int digitCount = 1;
while (i < N){ // go until all numbers between 1-N are checked
   for(;i < mul10; i++){ // go until reach the upper bound
      // do your part here
   }
   mul10 *= 10; // increase to next pow of 10
   digitCount++; // increases digit count
}

Level 41 , Sofia, Bulgaria

19 November 2020, 07:13

Seems like a good clue. I will have to ruminate on it, but I will figure out how it works. Thanks!

Guadalupe Gagnon

Level 37 , Tampa, United States

19 November 2020, 14:33

line 1: i is your counter; line 2-3: these variables will be for keeping track of how many digits the counter currently is line 4: main loop, goes as long as the counter is less than N lines 8-9 increase mul10 to the next power of 10 and digit count is increased by 1 line 5: this is the magic loop. It goes as long as the counter is below mul10. The first time it is reached 'mul10' equals 10, so this loop would go through the number below that: 1-9 then when the loop ends mul10 gets multiplies by 10 and digit count increases by 1. Then the while loop would start a new cycle. So here is how the first few times of the loop being reached would look: - digCount = 1; mul10 = 10; 'i' < mul10 would go through 1-9 - digCount = 2; mul10 = 100; 'i' < mul10 would go through 10-99 - digCount = 3; mul10 = 1,000; 'i' < mul10 would go through 100-999 - digCount = 4; mul10 = 10,000; 'i' < mul10 would go through 1,000-9,999 - digCount = 5; mul10 = 100,000; 'i' < mul10 would go through 10,000-99,999