ProjectEuler Problem 719 (some hints, but no spoilers)

-
Last time that I solved a ProjectEuler (PE) problem was in 2015...

This is their latest problem as of today: https://projecteuler.net/problem=719

Number Splitting

      

Problem 719

We define an S-number to be a natural number, n, that is a perfect square and its square root can be obtained by splitting the decimal representation of n into 2 or more numbers then adding the numbers.

For example, 81 is an S-number because 81=8+1.
6724 is an S-number: 6724=6+72+4.
8281 is an S-number: 8281=8+2+81=82+8+1.
9801 is an S-number: 9801=98+0+1.

Further we define T(N) to be the sum of all S numbers n≤N. You are given T(104)=41333.

Find 

The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat about the overall idea: 

First, understand that you're dealing with square root, and that the problem is asking for the solution for N=10^12. Use these two data points to understand a bit of the complexity that you want to achieve (don't try O(N), won't work). 

Second, think about how to write some code to, as quick as you can, check whether a number is an S-number. It won't be constant, but the numbers won't be that big either, and the complexity should be a polynomial of Log(number). Think recursively here to solve it. Think pruning the search for a solution (this function has to be fast, as fast as possible). 

Finally, please use long, not int.

When you put it all together, you should test against N=10^4 to make sure you're not going to be off by one or so (there are some weird cases when the numbers are small). Then, run against 10^12. It won't be instantaneous, but it should finish within 5min. In my case, it ran in about 90 seconds:

Running time: 00:01:25.1470336

Unfortunately, for the first time in this blog, no code to be shown since I want to respect the rules of engagement stipulated by PE. But I hope that the idea above gives you some direction. Cheers, ACC.


Comments

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more