Aim .the aim of this code is to print out all 9 digits numbers that have perfect squares .
all 9-digit perfect squares, if any, that uses all the digits 1 to 9 exactly once.
For example, 139,854,276 is a solution as 11,8262 = 139,854,276.

this is my own code but my run time is slow,


public class NineDigitPerfectSquare {
         private final static int BEGINNING=10000000;
         private final static int END=999999999;

public static void main(String[] args) {
//System.out.println(isPerfect(65));

String s= printPerfectNumbers();

for(int i=0;i<s.length();i++){
System.out.println(s.charAt(i));

}


}

public static boolean isOrdered(int []numbers){
// int value=1;
 

for(int i=0,value=1;i<numbers.length;i++,value++){
if(numbers[i]!=value)
return false;
}
return true;

}


public static void bubblesort(int[]numbers){
int temp=0;
for(int i=numbers.length-1; i>1;i--){
for(int j=0;j<i;j++){
if(numbers[j] > numbers[j+1]){
temp=numbers[j];
numbers[j]=numbers[j+1];
numbers[j+1]=temp;

}
}
}
}


public static int[] convertStringToIntArray(String s){
int permutation[]=new int[s.length()];
for(int i=0;i<permutation.length;i++)
permutation[i]= Character.digit(s.charAt(i),10);

return permutation;

}

public static boolean isPerfect(int n){


int x=1;
int sum=1;

while(sum<n){
x=x+2;
sum=sum+x;

}
return (sum==n);
   
}

public static boolean isPerfectSquare(int n){
return (Math.sqrt(n)==Math.floor(Math.sqrt(n)));
}



public static String printPerfectNumbers(){
int [] number1=new int[9];
String s=" "; String p="";
for(int i=BEGINNING ; i<=END ; i++){
if(isPerfectSquare(i) )
{
p=""+i;
// p.trim();
number1=convertStringToIntArray(p);
bubblesort(number1);
if(isOrdered(number1))
{
s=  s +  "  ,  " + i;
}

}
}
return s;
}
}

omotodun i would luv to be your programming  son lol,
please do you mind explaining this bit of your code

public static boolean isSet(String squared) {
      int[] tens_digit = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
      char c;

      for(int i = 0; i < 9; ++i)
         if((c = squared.charAt(i)) == '0' || ++tens_digit[c - 48] > 1)
            return false;

      return true;
   }

and also can you tell me if you know why my output was missing some results

That is pretty nifty, @omo_to_dun.

Very much correct that you can search over square roots rather than squares. And your hashing-like approach to testing that each number is contained in the set {0,, 9} is much cheaper than sorting.

So quite a bit faster than the original.

(Side comment: Isn't bubblesort really, really bad? Even if you want to use a slow N^2 sort, I thought you were supposed to use insertion sort, since it has better behavior [both better theoretical constants and better performance in the real world.] Also, does anyone know if bubblesort or insertion sort is actually faster in practice for a list of size 10? What do the Java libraries use on small lists?)

@ekt_bear

quicksort

I actually copied what i will paste here from the java 6 documentations of Arrays class,this is part of the description of all the overloaded sort methods


The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

I thought that insertion sort ends up being faster on small lists? Like here where the list of size 10, I'm wondering if it won't be slightly faster in practice, despite being N^2 to Qsort's NlogN.

(For example if insertion sort is say  N^2 and Qsort is 10NlogN, then you go with insertion sort for small lists on a list of size 20, since 20^2=400 is smaller than 10*20*log2(20) ~ 864.)

Hrm, here is what Wikipedia has to say:

Optimizations
Two other important optimizations, also suggested by R. Sedgewick, as commonly acknowledged, and widely used in practice are:[6][7][8]

- To make sure at most O(log N) space is used, recurse first into the smaller half of the array, and use a tail call to recurse into the other.
- Use insertion sort, which has a smaller constant factor and is thus faster on small arrays, for invocations on such small arrays (i.e. where the length is less than a threshold t determined experimentally). This can be implemented by leaving such arrays unsorted and running a single insertion sort pass at the end, because insertion sort handles nearly sorted arrays efficiently. A separate insertion sort of each small segment as they are identified adds the overhead of starting and stopping many small sorts, but avoids wasting effort comparing keys across the many segment boundaries, which keys will be in order due to the workings of the quicksort process. It also improves the cache use.

http://en.wikipedia.org/wiki/Quicksort

I suspect that this Quicksort implementation used in Java detects small lists and just runs insertion sort on them. Would have to read this paper you mentioned to be sure, though.

Thank you omotodun, Your a good teacher.I am still litttle bit confused on your algorithm but i would figure it tonight lol,

omo to dun, i like your reasoning

@omo to dun
Your sites registration doesn't work 100%, I received no email.

me need help with dis 1

$query = "SELECT b.*, u.nick, u.country, u.rate_sum FROM " . $DBPrefix . "bids b
LEFT JOIN " . $DBPrefix . "users u ON (u.id = b.bidder)


i wanna add another table called buyers with the same column WITH users

@omo_to_dun
good job!

You will not see the likes of Blacksta, Gbawe, Eko-Ile, Dayokanu, etc contributing in knowledgeable task like this. There own expertise is calling people names. Beaf I know has done something like this before and I was so impressed. Omo_to_dun also receive my resppect. Keep it up. It shows that NL is not only for names calling and insulting our leaders.

@Omo_to_dun,

Thanks for your time. I really appreciated the fact that u ran the code the user posted and even spotted the errors.

@ omo t0 dun happy weekend bros, just a small question
i am a little bit confused  with this part.i understand the [c-48] part but i cant see any character being passed into the c.
the only time a character is passed into the c is c = squared.charAt(i).i also dont understand how your increasing the frequency.

++tens_digit[c - 48] > 1

He assigns a value to c earlier in the line.

"++x" immediately increments the variable x.

If he instead did:

tens_digit[c - 48]++ > 1

Then you'd be checking the old value of tens_digit, not the incremented value.

thanks ekt