Project Euler Problem 98 Solution

Project Euler Problem 98 Solution

Anagramic Squares

by {BetaProjects} | Project Euler & HackerRank

Project Euler Problem 98 Statement

Solution

HackerRank version

HackerRank logo

Solves all test cases for Hackerrank Project Euler Problem 98

HackerRank Project Euler 98: 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.

Python Source Code

#print([961, 9216, 96100, 501264, 9610000, 73462041, 923187456, 9814072356, 98310467025, 985203145476, 9831140766225][input()-3])
import random
import math
from collections import defaultdict

def hash_function(s, hash_val):
    res = 0
    count = [0] * 10

    for char in s:
        c = int(char)
        count[c] += 1
        res += count[c] * hash_val[c]

    return res

def main():
    hash_val = [(i + 1) * random.randint(0, 11586) for i in range(10)]

    N = int(input())

    M = defaultdict(int)

    max_count = 0
    ans = 0

    start = math.ceil(math.sqrt(10 ** (N - 1)))
    end = math.floor(math.sqrt(10 ** N))

    for i in range(start, end + 1):
        s = i * i

        square = str(s)
        digits = sorted(square)
        digits_str = ''.join(digits)

        index = hash_function(digits_str, hash_val)

        M[index] += 1

        if M[index] > max_count:
            max_count = M[index]
            ans = s

    print(ans)

if __name__ == "__main__":
    main()

Last Word