# Project Euler #98: Anagramic squares

# Project Euler #98: Anagramic squares

LittleFox + 0 comments In python 3, getting a good quick hash for the squares was not obvious at all. I get 90 points in the 2 first tries. Then it took me more than 10 other tries to pass the last test case... But I finally did it :-)

nomail_forme + 1 comment Hint : The problem boils down to writing an acceptable hash method for anagramic strings. The last test case will fail with naive hash methods. Despite the same O(n) complexity for both methods, it makes a huge difference 2+s vs 0.64s.

drubanov + 0 comments Yes, I got about 50% drop in time from a better hash function. But before I went that way, tighter memory use gave me a 10% increase in speed. Still wasn't enough to get #10 though. Had to be very careful with memory and get the perfect (not near, but perfect) hash function here. The data range here actually allows for a PERFECT hash function.

nonanon + 2 comments I also find the question not-well defined. I suspect the association between words and numbers is misleading (since a list of English words would be required if each number

*really*had to correspond to a word) and instead is introduced as an analogy for the anagram of an arbitrary number (reordering of the decimal digits). Perhaps it is an intentional distraction to obfuscate the question.I could give a precise mathematical description of what I think is required, but (a) that probably wouldn't be in the spirit of the competition, (b) my code doesn't work, so my interpretation is likely to be wrong :-).

nonanon + 1 comment It would also help the problem description to explain the reason why 9216 is the solution for N=4. If I understand it correctly, it is because there are

*three*anagrams of 1296 that are squares: 1296, 2916, and 9216. There are no other "square anagram word sets" (a term that probably should be defined in the problem description) for numbers of length 4 that have as many elements as this set. 9216 is the largest element of this set, so it is the solution.Where there are multiple "square anagram word sets" that have the same maximal size for a different value of N. I presume you would take the largest square in the union of these sets.

javsjj + 1 comment By N=4 we have 9801(1089) is gt 9216 but not solution

ActonLB + 1 comment Remember that zeroes are not permitted so your solution is not valid or at least thats the only reason I can think of why its not valid

nonanon + 1 comment (I worked out the meaning and my code is succcessful now)

*Leading*zeros are not permitted, but other zeros are permitted. The reason 9801 is not the solution is that its "square anagram word set" only has*two*elements, whereas 9216's has*three*.If 0189 were also a square then 9801 would still not be the solution, since anagrams with

*leading zeros*are not counted in the "square anagram word set".However, if instead 1089 were also a square, then 9801

*would*be the solution, as its "square anagram word set" would have*three*elements, tying with 9216's.javsjj + 1 comment 33*33=1089

nonanon + 1 comment Whoops! You are right; 9801 and 1089 are the two squares. I meant if 1098 (or some other anagram not starting with 0) were another square, then there would be three solutions.

kdimou + 1 comment Why the 1089 ~ 9801 pair is not the right solution for N=4?

4

32^2 = 1024 ~ 49^2 = 2401

33^2 = 1089 ~ 99^2 = 9801 <<<< largest square number

36^2 = 1296 ~ 54^2 = 2916

36^2 = 1296 ~ 96^2 = 9216

37^2 = 1369 ~ 44^2 = 1936

42^2 = 1764 ~ 69^2 = 4761

54^2 = 2916 ~ 96^2 = 9216

64^2 = 4096 ~ 98^2 = 9604

9801

zquanghoangz + 1 comment The biggest number in the largest set. Set of 9216 have 3 numbers in set

ActonLBAsked to answer + 1 comment Ok so for what I read the deal goes like this: given an integer N your goal is to find an integer of N digits where neither one of them is either zero or repeated, check if this digit is a perfect square and then rearrange these digits until you find the largest perfect square with those same digits. As for the words "CARE & RACE" in the description it seems they only wanted to use them as an example of what an anagram is. This is my humble conclusion of the problem, I could be wrong in something.

nonanon + 0 comments It is confusing, but I finally worked it out:

Zeros are permitted (as are repeated digits), but anagrams with a leading zero are not included in each "square anagram word set". We are looking for the biggest (greatest number of elements) square anagram word sets and then within those the greatest element.

melwyn95 + 0 comments I followed a simpler approach, I precomputed all the answers and stored it, and just responded to the queries...

for the hash function i used the descending order of digits.

bhavikgevariya + 1 comment 961 , 9216 , 96100 , 501264 , 9610000 , . , . , . , . , . , .

bhavikgevariya + 0 comments next is

*73462041*for**8**? &*923187456*for**9**?

kitchent + 0 comments This is not very interesting at all. Tried using a list of primes for better hashing, and turned to

`ord`

instead of`int`

. Gave up on`defaultdict`

for minor improvement. Still no clue. I'm not sure if it the the mindset to iterate from`3162278`

to`1000000`

that is wrong in itself.

gaurya95 + 0 comments Hi! I am getting only one correct test case. Can anyone help me where I might be going wrong? I have used the correct logic according to myself. If you want I can provide code too. I have used Hashtable in java in this code.

import java.io.

*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*;public class Solution { public static boolean isAna(int a,int b){

`int []hash=new int[10]; int c=0; while(a>0) {hash[a%10]++;a=a/10;} if(hash[0]>0) return false; while(b>0) { hash[b%10]--;b=b/10;} for(int i=0;i<10;i++) if(hash[i]!=0) return false; return true; } public static int max(int ... m){ int max=0; for(int i=0;i<m.length;i++){ if(max<m[i]) max=m[i]; } return max; } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int N=sc.nextInt(); int a=(int)Math.floor(Math.sqrt(Math.pow(10,N-1))); int b=(int)Math.floor(Math.sqrt(Math.pow(10,N))); int temp=0; Integer m=0; Hashtable<Integer,Integer> maximum=new Hashtable<Integer,Integer>(); for(int i=a;i<b-1;i++){ for(int j=i+1;j<b;j++){ if(isAna(i*i,j*j)){ if(!maximum.containsKey(i*i) || !maximum.containsKey(j*j)) maximum.put(Math.max(i*i,j*j),2); else {if(maximum.containsKey(i*i)){ temp=maximum.get(i*i);maximum.remove(i*i);} if(maximum.containsKey(j*j)){ temp=Math.max(temp,maximum.get(j*j));maximum.remove(j*j);} maximum.put(Math.max(i*i,j*j),temp+1); } } } } Set set=maximum.entrySet(); Iterator i=set.iterator(); Map.Entry p=null; while(i.hasNext()){ Map.Entry me=(Map.Entry)i.next(); if((Integer)me.getValue()>m) {m=(Integer)me.getValue();p=me;} } System.out.println(p.getKey()); }`

}

ms_shiva90 + 0 comments Time OUT ERROR : testcase 4 and above..

Code worked for testcase 0 ,1,2,3. Stuck!! :(I calculated all permutaions of the number which had perfect square root and added the permutation which had perfect sqroot and found the largest list and printed out its largest number.

import java.io.

*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*;public class AnagramicSquares {

`public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ List<List<String>> ans_set = new ArrayList<List<String>>(); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); double init = Math.pow(10.0 ,n) - 1; double min = Math.pow(10.0,n-1); for(double i = init;i > min-1;i--) { double sqrt = Math.sqrt(i); //shud be a integer if(sqrt % 1 == 0) { //chk for perfect sqrt in its anagram except leading zeroes List<String> li = check(String.valueOf((int)i)); if(li != null) { ans_set.add(li); } } } int max_index = 0; int maxSize = 0; for(int i=0;i < ans_set.size(); i++){ List<String> li = ans_set.get(i); int size = li.size(); if(size > maxSize){ maxSize = size; max_index = i; } } System.out.println(ans_set.get(max_index).get(0)); } public static List<String> check(String val) { int n = val.length(); List<String> li = new ArrayList<String>(); for(int i = 0; i < n; i++) { String initialLetter = String.valueOf(val.charAt(i)); if(!initialLetter.equals("0")){ permute(initialLetter, val.substring(0,i)+val.substring(i+1,n),li); } } if(li.size() == 1) return null; else { return li; } } public static void permute(String part, String rem,List<String> li) { //add only those permutations which math squares i.e it has a square root integer if(rem.equals("")){ int ans = Integer.valueOf(part); //check for decimal values if(Math.sqrt(ans) % 1 == 0) { //check if the number is already present in the list for we dont want repetitions i.e 7744 , 7744 if(checkNoRepeatExists(part,li)) li.add(part); } } int n = rem.length(); for(int i=0;i<n;i++){ permute(part+String.valueOf(rem.charAt(i)), rem.substring(0,i)+rem.substring(i+1,n),li); } } private static boolean checkNoRepeatExists(String part, List<String> li) { // TODO Auto-generated method stub for(String str : li){ if(str.equals(part)) return false; } return true; }`

}

ms_shiva90 + 0 comments My code gets timed out for testcases 5 and above.

I have no clue how to do this quicker???. I computed all permutations of a N digit number if the number had a perfect square root and all the permutations which were square roots as well were added to a list.

In the end I took the largest list and printed out the largest number in the list. Complexity was O(N)+O(mk!)

where N is input. m is number of perfect squares and k! to generate all permutations of the given number in m.

zack_kenyon + 1 comment this is perhaps the most poorly worded question I have ever read without being wrong. who does quality control on these?

shashank21jHackerRank AdminChallenge Author + 1 comment Can you tell which part needs better wording?

zack_kenyon + 1 comment yeah sure, Here it is.

"By replacing each of the letters in the word CARE with 1,2,9, and 6 respectively, we form a square number: 1296=36^2. What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216=96^2. We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.

What is the largest square number formed by the largest set of anagrams of the given length?"

instead try:

"some square numbers are numerical anagrams of other square numbers. For instance, 1296=36^2 and 9216=96^2. The set of square anagrams of 1296 is [1296, 9216]. For each value of N, we wish to know the largest set of square anagrams for a number with N digits. . Print out the largest number of this set. If the largest set is not unique, pick whichever one has the largest maximum element."

shashank21jHackerRank AdminChallenge Author + 0 comments updated. Didn't realize as I use same statement from PE. And here we are not using the words hence doesn't make sense.

Sort 16 Discussions, By:

Please Login in order to post a comment