I am pretty sure that this will pass verification once I change the return to the correct result array.
I really wanted to understand what this code did before I used it to pass verification. I dug into it as well as I could and tried to parse out how it was working. I had already written my own code for this task, and it worked, but it was not getting verified. The only reasons that I can figure, and this was with others help, is that my code was too slow and used up too much memory. So I too turned to this code that everyone else is using for this task. But it bothered me that I didn't understand it. So here is what I have been able to figure out. I put comments line by line as to what I thought was happening.
Also here is a table to use if you wanted to walk through it.
![]()
I would love any feedback or corrections. Or especially any more clarity.
I would love any feedback or corrections. Or especially any more clarity.package com.codegym.task.task20.task2025;
import java.util.Arrays;
import java.util.Iterator;
import java.util.TreeSet;
/*
Number algorithms
*/
public class Solution {
public static long[] getNumbers(long N) {
if(N <= 0)return new long[0];
int digits = 1 + (int)Math.log10(N);
if(N == 0) digits = 1; // determines the number of Digits in the number.
genpow(digits +1); // Create the Table of factor values that goes 1 higher
// than the number of digits in our number
numbers = new TreeSet<>(); // Array to hold found numbers
for(int i = 1; i <= digits; i++){ // For the number of digits in our number
try{ // We run the search() incrementing i, which is N in the
search(i, 1, 0, 0); // search() method
}catch (Exception e){
System.out.println("hau phan van: " + i);
}
}
Iterator<Long> iter = numbers.iterator(); // go through and remove all numbers that are
while (iter.hasNext()){ // greater or equal to the target number
long l = iter.next();
if( l >= N) iter.remove();
}
long[] result = new long[numbers.size()-1]; // create a new array and move
int i = 0; // all the values to it except 0
for(long l: numbers) {
if(l!=0) {
result[i] = l;
i++;
}
}
long[] fakeresult = new long[1];
return fakeresult;
// return result; //********************* I commented this out so that it wouldn't pass ******
}
// THis part is very difficult to wrap my head around.
// Essentially what it does, I THINK, is to go through the table of powers
// that was created and send every number to be checked by the checker
// then if the checker says it is an Armstrong number it adds it to the numbers array.
// this creates recursive searches // which confuses me and makes my head hurt
// N = (int N = 1; N <= digits; N++) this search is done
// for the number of digits in the original number times so each N passed represents the next successive
// Search start values search( N, d=1, pow=0, index=0);
public static void search(int N, int d, long pow, int index) {
if (d == N + 1) { // when d = The current N + 1 this determines if the
//value passed was from the correct row in the table
// If it is then it checks to see if
if (check(pow)) { // the passed pow is An Armstrong number
numbers.add(pow); // if so then add it to the numbers array
} // Otherwise we are going to generate searches for the next row. I think..
//return;
} else { // We were not looking at the correct row
// so we are going to look up the next row of values
for (int i = index; i < 10; i++) { // Start up 9 more searches one for each column all for the same row.
try {
// each successive recursion will start on the next index and will
search( // look at the next row of values
N, // using the same N which is the row we are looking for
d + 1, // increment d, and pass it until d == the current N +1, remember d is tracking which row we are looking at.
pow + pows[i][N - 1], // pass the value found in the table to pow to be checked in the next recursion.
i // passes i to become the next index
);
// this is where my mind melts a bit.
} catch (Exception e) { // each search either ends above or it creates a number of new searches for the next row.
// each of which does the same.......
}
}
} // return and start a new N
}
public static boolean check(long number) { // Checks to see if this number is an Armstrong
long temp = number; // create a copy to manipulate
digits = new int[10]; // array for tracking the number of each digit occurance
int n = 0; // counter to count how many digits
long sum = 0; // for the resulting number to match
while (temp > 0) { // We are going to tear digits off of temp till it is gone
int digit = (int) (temp % 10); // find the first digit in the one's column
digits[digit]++; // increment that number in the digits array
n++; // counts how many digits were there.
temp /= 10; // divide temp by 10 so that you can work on the next digit
}
if (number == 0) n = 1;
for (int i = 0; i < 10; i++) { // go through the digits array and for each digit found add
sum += digits[i] * pows[i][n - 1]; // that digit to the power of n-1 times the number of times it was found
} // n-1 is the reference for the power of n in pows
if (sum == number) return true;
return false;
}
static TreeSet<Long> numbers;
static long[][] pows;
static int digits[];
public static void genpow(int m) { // creates a table of factor values for 0-9
pows = new long[10][m]; // for the number of digits in a number
for (int i = 0; i < 10; i++) { // up to the number of digits in the original number
long p = 1; //
for (int j = 0; j < m; j++) {
p *= i;
pows[i][j] = p; // where i = the digit and j = the place holder value/ factor
}
}
System.out.println(Arrays.deepToString(pows));
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
long arr[] = getNumbers(1294039587l);
System.out.println(System.currentTimeMillis() - start);
for (long l : arr) {
System.out.println(l);
}
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
System.out.println(arr.length);
long a = System.currentTimeMillis();
System.out.println(Arrays.toString(getNumbers(10)));
long b = System.currentTimeMillis();
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
System.out.println("time = " + (b - a) / 1000);
}
}