Cannot pass the verification

Question about the task

Resolved

I tried two methods to limit the time to 10 seconds, but after a lot of googling I can't find anyway to limit the memory use. I tested in the main, either way works for the time control, but the verification still times out. Any suggestions please? Thanks in advance.

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.concurrent.*; /* Number algorithms */ public class Solution { public static long[] getNumbers(long N) throws InterruptedException { long[] result = null; Find find = new Find(N); Thread t = new Thread(find); t.start(); Thread.sleep(10000); t.interrupt(); // ExecutorService executor = Executors.newSingleThreadExecutor(); // ScheduledExecutorService canceller = Executors.newSingleThreadScheduledExecutor(); // Future f = executor.submit(find); // try { // f.get(10, TimeUnit.SECONDS); // } catch (ExecutionException e) { // e.printStackTrace(); // //System.out.println("over1"); // executor.shutdownNow(); // } catch (TimeoutException e) { // // System.out.println("over2"); // executor.shutdownNow(); // } result = find.list.stream().mapToLong(l -> l).toArray(); return result; } public static class Find implements Runnable{ long n; ArrayList<Long> list = new ArrayList<>(); public Find(long N) { n=N; } @Override public void run() { for (long s=0; s<n; s++) { if(Thread.currentThread().isInterrupted()){ //System.out.println("over"); return; }else { String ss = String.valueOf(s); int m = ss.length(); char[] numbers = ss.toCharArray(); long sum =0; for (char c: numbers) { //System.out.println(c); sum += Math.pow((c-48), m); } if (sum==s) { list.add(s); } } } } } public static void main(String[] args) throws Exception { // long[] rrr= getNumbers(50000000); // System.out.println(Arrays.toString(rrr)); } }

Comments (5)

Popular
New
Old

You must be signed in to leave a comment

Bill Wu

Level 29 , Wellington, New Zealand

22 March 2019, 00:04

Hi guys, with Guadalupe's help, I solved with the code from Github. I got the idea of check the number set to reduce time. But after thinking for a few days, I still can't understand the code static void search(int digit, int unused, long pow) can anyone explain it please? Thanks a lot.

Guadalupe Gagnon

Level 37 , Tampa, United States

14 March 2019, 14:03

By removing the math.pow, and a few modifications, I got my code down to 1.7 seconds and still it failed. I will message you with how I solved it. This was my code:

public static long[] getNumbers(long N) {

        long tempII = N;
        LinkedHashSet<Long> narcNums = new LinkedHashSet<>();

        long tempResult;
        long digitLengthTemp = 10;
        long tempI;
        long[] powers = {0l, 1l, 2l, 3l, 4l, 5l, 6l, 7l, 8l, 9l};

        for (long i = 0; i < N; i++) {
            if (i == digitLengthTemp) {
                digitLengthTemp *= 10;
                for (short x = 2; x < powers.length; x++) powers[x] *= x;
            }
            //set value of top digits of numbers past first 3 to a remedial value
            tempI = i;
            long remedialValue = 0;
            tempI /= 10; tempI /= 10; tempI /= 10;

            while (tempI > 0) {
                short index = (short) (tempI % 10);
                remedialValue += powers[index];
                tempI /= 10;
            }
            //only passes 1000 at a time to this loop and adds each result to remedial top half
            for (int j = 0; j < (tempII > 1000 ? 1000 : tempII); j++) {
                //sets digit length and increases the values in array
                if (i == 0 && j == digitLengthTemp) {
                    digitLengthTemp *= 10;
                    for (short x = 2; x < powers.length; x++) powers[x] *= x;

                }
                //resets temp results
                tempResult = remedialValue;
                tempI = j;


                //gets the sum of each (digit^numberLength) of number passed to it
                while (tempI > 0) {
                    if (tempResult > i + j) break;
                    short index = (short) (tempI % 10);
                    tempResult += powers[index];
                    tempI /= 10;
                }

Guadalupe Gagnon

Level 37 , Tampa, United States

14 March 2019, 14:03

//checks if sum equals original number
                if (i + j == tempResult) narcNums.add(i + j);
            }
            i += 999; // adds to i in increments of 1000
            tempII -= 1000;
        }

        //converts to long array
        long[] results = new long[narcNums.size()];
        short i = 0;
        for (long x : narcNums) {
            results[i++] = x;
        }
        return results;
}

Guadalupe Gagnon

Level 37 , Tampa, United States

14 March 2019, 14:13

I realized that I was using math.pow by the same power literally millions of times in a row. For example, lets say you reach 1 million, for that number then that number +1, then +2, then + 3 etc you have to math.pow each digit by 10 all the way up to 9,999,999. Then when you reach 10 million up to 99 million you have to math.pow each digit by 11. I created an array that holds all the math.pow for each digit (0-9) at line 9. Lines 12-14 increases those values by multiplying each by its index every time the number of digits increases. So, when you are at 1 million, that array holds the values: [0 pow 9, 1 pow 9, 2 pow 9, 3 pow 9, 4 pow 9, etc]. Then lines 40-41 gets each digit of the test number and pulls the number for that digit stored in the array to add to the sum for testing, effectively eliminating the need for math.pow. Try it out and see if you can figure out how it works. It runs with 100,000,000 numbers on my computer in ~1700 milliseconds

Guadalupe Gagnon

Level 37 , Tampa, United States

14 March 2019, 14:41

I did take a look at your code and something that I see as a problem is that it will runs for 10 seconds no matter what. If want to find all numbers in 1-100, it will complete the loop in ~100 ms, but you don't interrupt the Thread.sleep(10000) at that point and it won't return the Array and finish the program until that sleep is done.