@Arpit: Actually, we didn't go over all of the values. The question asks about 10-digit perfect squares that have non-repeating digits. So n = 10^10-10^9. The brute force algorithm really would take a look at all n of those numbers and pick out the ones that both were perfect squares and had non-repeating digits. This would be an O(n) algorithm. Another, less brute-forceish, way to do it would be to look at all 9*9! 10-digit numbers that have non-repeating digits and pick out the ones that are perfect squares. This appears to be o(n), which is < O(n); I suppose you could use Stirling's Approximation to state the complexity more precisely. Finally, the algorithm I used looks only at the 10-digit perfect squares and picks out the ones that have non- repeating digits. This is O(sqrt(n)).
Dave On Feb 25, 12:29 pm, Arpit Sood <[email protected]> wrote: > its just that i wanted to learn some other way too, where we don't go > linearly over all values > > > > > > On Fri, Feb 25, 2011 at 11:54 PM, Dave <[email protected]> wrote: > > @Arpit: Is there any requirement to do it other than by brute force? > > Besides, I think it is rather clever brute force. > > > Dave > > > On Feb 25, 5:13 am, Arpit Sood <[email protected]> wrote: > > > dave how is this different from brute force ? > > > > On Thu, Feb 24, 2011 at 8:56 PM, Dave <[email protected]> wrote: > > > > @Ashish: The code seems pretty straightforward, but okay. The outer > > > > for-loop runs through the numbers that have 10-digit squares. The > > > > squares are represented as 64 bit integers (type long long) because > > > > some of them are larger than the maximum representable 32-bit > > > > integers. For each number, the inner for-loop makes a tally of which > > > > digits appear in the square of the number. The if-statement determines > > > > whether the tally indicates that the square of the number has all ten > > > > digits, in which case the digits are non-repeated as prescribed in the > > > > problem statement. > > > > > Dave > > > > > On Feb 24, 5:25 am, ashish agarwal <[email protected]> > > > > wrote: > > > > > @dave..Can you please explain your logic .. > > > > > Regards, > > > > > Ashish > > > > > > On Thu, Feb 24, 2011 at 6:32 AM, Dave <[email protected]> > > wrote: > > > > > > Try this: > > > > > > > int i,k,n; > > > > > > long long j,nsq; > > > > > > for( n = 31623 ; n < 100000 ; ++n ) > > > > > > { > > > > > > nsq = (long long)n * (long long)n; > > > > > > j = nsq; > > > > > > k = 0; > > > > > > for( i = 0 ; i < 10; ++i ) > > > > > > { > > > > > > k |= (1 << (j % 10)); > > > > > > j /= 10; > > > > > > } > > > > > > if( k == 01777 ) > > > > > > printf("%i %lli\n",n,nsq); > > > > > > } > > > > > > > It finds 76 answers in the blink of an eye, the first being 32043^2 > > > > > > and the last being 99066^2. > > > > > > > Dave > > > > > > > On Feb 22, 3:17 pm, bittu <[email protected]> wrote: > > > > > > > How to find a number of 10 digits (non repeated digits) which is > > a > > > > > > > perfect square? perfect square examples: 9 (3x3) 16 (4x4) 25(5x) > > etc. > > > > > > > Ten digit number example 1,234,567,890 > > > > > > > > Thanks & Regards > > > > > > > Shashank > > > > > > > -- > > > > > > You received this message because you are subscribed to the Google > > > > Groups > > > > > > "Algorithm Geeks" group. > > > > > > To post to this group, send email to [email protected]. > > > > > > To unsubscribe from this group, send email to > > > > > > [email protected]. > > > > > > For more options, visit this group at > > > > > >http://groups.google.com/group/algogeeks?hl=en.-Hidequoted text - > > > > > > - Show quoted text - > > > > > -- > > > > You received this message because you are subscribed to the Google > > Groups > > > > "Algorithm Geeks" group. > > > > To post to this group, send email to [email protected]. > > > > To unsubscribe from this group, send email to > > > > [email protected]. > > > > For more options, visit this group at > > > >http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > > Regards, > > > Arpit Sood- Hide quoted text - > > > > - Show quoted text - > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Regards, > Arpit Sood- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
