Actually I am getting sharp result. It works fast and doesn't take much memory

Question about the task

Under discussion

Actually I am getting sharp result. It works fast and doesn't take much memory, but during the verification it hangs - "The program ran too long and was closed!"

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; /* Number algorithms */ public class Solution { public static long[] getNumbers(long N) { long[] result; List<Integer> digits = new ArrayList<>(); List<Long> results = new ArrayList<>(); for (long i = 0; i < N; i++) { long toSplit = i; int count = 0; while (toSplit > 0) { digits.add((int) toSplit % 10); //split into digits and store them into List toSplit /= 10; count++; //get number of digits and needed power number } long sum = 0; for (int j = 0; j < count; j++) { sum += Math.pow(digits.get(j), count); // make this : 3*3*3 + 7*7*7 + 0*0*0 } if (sum == i) { results.add(i); // check if this is true 370 == 3*3*3 + 7*7*7 + 0*0*0 and add it to List } digits.clear(); } result = new long[results.size()]; for (int i = 0; i < result.length; i++) { result[i] = results.get(i); } return result; } public static void main(String[] args) { //getNumbers(10000); long a = System.currentTimeMillis(); System.out.println(Arrays.toString(getNumbers(9223372L))); 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 (8)

Popular
New
Old

You must be signed in to leave a comment

Justin Smith

Level 41 , Greenfield, USA, United States

22 November 2021, 03:11

I have run into the same problem, and I think the real trick here is that if N is large enough, it can't even finish exiting the loop's current iteration before the validation says "too long". In other words, it starts an iteration with time < 10 so it allows that iteration to proceed, but it gets bogged down in the inner loops long enough that the time = 10 + some number large enough to make the validation quit. Guadalupe's procedure is really good (I mean it's brilliant), but I think part of the point of this lesson is to have it run out of time while trying to calculate for a large N, and be able to handle exiting the loop and showing what it got within that time constraint. If you create a solution that is able to calculate all the numbers for any Long value, then you lose out on the educational component of half the task. I think what is really wanted is a way to have the loop terminate as soon as it hits 10 seconds or 50MB, without completing the current iteration of the loop. The problem with most loops (for, while, do-while) is that they check a condition at one end of the iteration, but not continuously during the iteration, which is what is needed. You could maybe use a conditional in the loop with continue to make it jump to the end of the iteration. Alternately, I feel like there may be a way to do this using a Thread, since this would allow it to constantly check the time and memory while it's calculating numbers.

Justin Smith

Level 41 , Greenfield, USA, United States

22 November 2021, 03:17

You know, now that I took another look at the conditions, I think I may have it wrong. I assumed it wanted us to just get what we can within 10 seconds and 50 MB. But now I think it means simply that it must get all of them and it must take no longer than 10 seconds or 50 MB.

Guadalupe Gagnon

Level 37 , Tampa, United States

5 March 2021, 15:04

This task is not a beginner task, and the requirements need to be lightened up. While you may think that your code runs fast, the higher the number goes the longer it takes. I tested this code with Integer.MAX_VALUE and it took 11 minutes to complete. For comparison, the code I have (which has taken me over a year to create btw) can find all the numbers between 1 and Long.MAX_VALUE in 800 milliseconds. I'll explain what I do: #1 I cache the values of Math.pow in a long array. This array increases the values every time you move up a digit, so: between numbers 1-9 it hold the result of each digit pow(#, 1) {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} numbers 10-99 hold each digits pow(#, 2) {0, 1, 4, 9, 16, 25, 36, 49, 64, 81} numbers 100-999 each digits pow(#,3) {0, 1, 8, 27, 64, 125, 216, 343, 512, 729} etc... Always getting the digit, using pow(), adding the results, then checking the number is slow. If you only use pow() one time then just keep reusing the stored results the algorithm speeds up considerably #2 I have a second long Array that starts at length one, then resizes to add one index every time the number goes up a digit. I store the running results of each digit of the current number in this array, with the left most index matching up to the left most digit in the test number. So take 370 as an example. This array stores: index 0 index 1 index2 {pow(3,3) = 27, index[0] + pow(7,3) = 370, index[1] + pow(0,3) = 370} The right most index will store the total result. Now, the thing about this is when we move to 371 all you have to do is replace the right most index with the result of index[i-1] + pow(1,3). By only doing new math on the new digits in the number effectively caches the results and saves a ton of cpu cycles. On numbers you could either do 1 math operation per 1 number increase or number.length math operations per 1 number increase.

Guadalupe Gagnon

Level 37 , Tampa, United States

5 March 2021, 15:24

#3 I only check each number of unique digits. Take 371 as an example. If you take pow(3,3) + pow(7,3) + pow(1,3) this will result in 371 You will also get the same exact result for 137, 173, 317, 713, and 731. You don't need to check all of those numbers. Basically, the number of different combinations of numbers with unique digits is going to be factorial number.length (so 3! for a 3 digits number; 20! for a 20 digit number). The trick is, once you increase a digit in a number, you take that digit all the way to the left in the number, so take this example: 3499 when you increase the number by 1 it becomes 3500, but you would carry the 5 all the way to the right, so the next number would actually be 3555 instead. #4 I found it easier to create an int Array to store my digits instead of using long variable. Every time a new digit is added I increased the length of the Array and started its digits all at 0. So when I was in 4 digit numbers I would have a starting array of {0, 0, 0, 0} then I started the algorithm by using tip #3. When I was done with the 4 digit numbers the new array would be {0, 0, 0, 0, 0} #5 Testing each result can be tricky if the numbers don't match. Take 371 for example. My algorithm would find this at number 137. I would check the digits against the pow results by counting each digit in one number, then taking those counts and subtracting them out with the digits of the second number. I used an int{} of length 10 (each index 0-9 would be a digit 0-9). So I would count each digit in 137 and use it to increase the that index by 1: array[1]++ array[3]++ array[7]++ and end up with the array: {0 , 1, 0, 1, 0, 0, 0, 1, 0, 0} Then take each digit in 371 and do the same except subtract 1: array[3]-- array[7]-- array[1]-- and end up with: {0 , 0, 0, 0, 0, 0, 0, 0, 0, 0} If the array wasn't all 0, then the numbers wouldn't match. If it did end up all 0's I would add the result to my results list.

Dmitri

Level 22 , Seversk, Russia

9 March 2021, 10:59

I am very much impressed by the thoroughness of your approach, I see you spend much time reflecting on this algorithm. If the reason is in time (which was actually given in the task, and my time was not greater than that, and in the task it was not said that you should test .MAX_VALUE) then I'll try to improve my algorithm to make it faster. Do you think this is Math.pow part that takes the most time?

Dmitri

Level 22 , Seversk, Russia

9 March 2021, 12:21

I replaced Math.pow with my own method

public static long myPow(int x, int y) {
        if (y == 0) return 1;
        long result = x;
        for (int i = 1; i < y; i++) {
            result *= x;
        }
        return result;

And changed line 18 to

for (long i = 1; i < N; i++) {

Now the validator does not hang but still the third condition - The getNumbers method must return the array of numbers that satisfy the task conditions - is not satisfied. That confuses me because I checked my numbers for being armstrong...

Lisa

Level 41

22 November 2021, 10:26

Cause Justin brought this up again I rethought my initial approach and came up with something different. Unfortunately I can not test this anymore. My current approach is based on my assumption that we have a time complexity of O(n). And this is not bad at all. So what has to be done is, to reduce the time consumption per iteration. And voila, Lupe, you gave me the link to your dynamic coding video. So I tried the last hour to cache (partial) results. And what is easy to cache and takes a lot of time? Calculating the Nth power of each digits in each iteration. So each time we step over 10 pow x I refresh the cash. Here I also get the number of digits of the current iteration so I just need to loop over those, get the cached pow result and compare the sum with the current iteration. If you precalc all powers you can increase speed again. One just needs to create a matrix instead of a single dim cache array and you're rid of the check in each iteration if the current iteration stepped over a 10 pow n border. On my notebook I get those results I omitted your suggestion to not calculate result for 'unique digits' as this seems to much effort for not much gain (if all) (see assumption above, O(n)). 10_000_000 -> 0s 100_000_000 -> 1s 1_000_000_000 -> 17s, mem should be approx 4mb here (not much as I just have a list to hold the result and 10 cached values).

[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]
memory 568
time = 17

What do you think... it's not super fast but not bad either?

Lisa

Level 41

22 November 2021, 10:28

public static long[] getNumbers(long N) {
    List<Long> res = new ArrayList<>();

    // cache initialization related stuff
    int tenth = 10;
    int digits = 1;
    long[] cache = new long[10];
    fillCache(1, cache);

    // start iterating up to N
    long sum;
    for (int i = 1; i < N; i++) {
        // first take care of the cache, check if we need to update it
        if (i % tenth == 0) {
            digits++;
            tenth *= 10;
            fillCache(digits, cache);

        }
        // now create sums of single digits pow numlength
        sum = 0;
        int currIteration = i;
        for (int j = 0; j < digits; j++) {
            sum += cache[currIteration % 10];
            currIteration /= 10;
        }

        // if we have a match, add it
        if (sum == i)
            res.add((long) i);
    }


    long[] result = new long[res.size()];
    for (int i = 0; i < res.size(); i++)
        result[i] = res.get(i);

    return result;
}

public static void fillCache(int power, long[] cache) {
    long result;
    int p;

    for (int i = 1; i < cache.length; i++) {
        result = 1;
        p = power;
        // get the power
        while (p-- > 0)
            result *= i;
        cache[i] = result;
    }
}