[Golang] Pandigital products - Problem 32 - Project Euler
source link: http://siongui.github.io/2018/10/21/go-pandigital-products-problem-32-project-euler/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Golang] Pandigital products - Problem 32 - Project Euler
October 21, 2018
Problem: [1]
We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.
Solution:
The form of the identity must be like:
M * MMMM = MMMMMM * MMM = MMMMBrute-forcely check all permutations [2] of 1~9 in above form. We will get the following satisfying identity.
12 * 483 = 579618 * 297 = 534627 * 198 = 534628 * 157 = 439639 * 186 = 725442 * 138 = 57964 * 1738 = 69524 * 1963 = 785248 * 159 = 763256370
package main import ( "fmt" "strconv" ) var sum int64 = 0 // Swap the i-th byte and j-th byte of the string func swap(s string, i, j int) string { var result []byte for k := 0; k < len(s); k++ { if k == i { result = append(result, s[j]) } else if k == j { result = append(result, s[i]) } else { result = append(result, s[k]) } } return string(result) } // Function to find all Permutations of a given string str[i:n] // containing all distinct characters func permutations(str string, i, n int) { // base condition if i == n-1 { checkProduct(str) return } // process each character of the remaining string for j := i; j < n; j++ { // swap character at index i with current character str = swap(str, i, j) // recursion for string [i+1:n] permutations(str, i+1, n) // backtrack (restore the string to its original state) str = swap(str, i, j) } } // MxMMMM=MMMM // MMxMMM=MMMM func checkProduct(s string) { // check M x MMMM = MMMM m1, _ := strconv.ParseInt(s[0:1], 10, 0) m2, _ := strconv.ParseInt(s[1:5], 10, 0) prd, _ := strconv.ParseInt(s[5:9], 10, 0) if m1*m2 == prd { fmt.Printf("%d * %d = %d\n", m1, m2, prd) sum += prd } // check MM x MMM = MMMM m1, _ = strconv.ParseInt(s[0:2], 10, 0) m2, _ = strconv.ParseInt(s[2:5], 10, 0) prd, _ = strconv.ParseInt(s[5:9], 10, 0) if m1*m2 == prd { fmt.Printf("%d * %d = %d\n", m1, m2, prd) sum += prd } } func main() { str := "123456789" permutations(str, 0, len(str)) fmt.Println(sum) }
Test on:
- Ubuntu 18.04, Go 1.11.1
- Go Playground
References:
[3][Golang] Lexicographic permutations - Problem 24 - Project Euler
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK