ProjectEuler Problem 52: Permuted multiples

ProjectEuler Problem 52: Permuted multiples

Jul 14, 2021
Coding
ProjectEuler

Problem 52: Permuted multiples #

https://projecteuler.net/problem=52

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

分析 #

找到最小的整数 x,满足 x, 2x, 3x, 4x, 5x, 6x 包含相同的数字

题目相对比较简单,可做简单的遍历即可。 但是为了提高遍历的效率,我们不用遍历每一个数。

方法 遍历求解 #

从 x = 11 往上遍历,对于每一个 x,做如下处理:

  • (1) 判断 x 和 6x 的位数是否相同;如果不相同跳转到 (2),如果相同跳转到 (3)
  • (2) 不相等时,在 x 位数不变的情况下,随着 x 的增大,两者更不可能相等, 所以,此时需要给 x 增加位数。 如 x = 17,6x = 102,此时 18~99 都可以直接跳过了,直接跳到下一个位数的起始点 x = 100。 增加位数后,再跳转会(1)
  • (3) 依次获取 x, 2x, 3x, 4x, 5x, 6x 的所有排序好的数字列表,判断是否都相等,如果全都相等,则找到了答案,输出,结束。 如果不全相等,x++ 继续 步骤 (1)。

C++ #

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

int getLen(int n)
{
    int len = 0;
    while(n > 0){
        len++;
        n /= 10;
    }

    return len;
}

std::vector<int> getDigitsSorted(int n)
{
    std::vector<int> digits;
    while(n > 0){
        digits.push_back(n % 10);
        n /= 10;
    }
    std::sort(digits.begin(), digits.end());

    return digits;
}

bool hasSameDigits(const std::vector<int>& v1, const std::vector<int>& v2)
{
    if(v1.size() != v2.size()) return false;

    for(int i = 0; i < v1.size(); i++){
        if( v1[i] != v2[i]) return false;
    }

    return true;
}

int main()
{
    int x = 11;
    while(true){
        // 判断 x 和 6x 的位数是否相等
        int lenX = getLen(x);
        int len6X = getLen(6*x);

        // 如果不相等,在 x 位数不变的情况下,随着 x 的增大,两者更不可能相等
        // 所以,此时需要给 x 增加位数
        // 如, x = 17,6x = 102,此时 18~99 都可以直接跳过了,直接跳到下一个位数的起始点 x = 100,再继续处理
        if(len6X > lenX){
            x = (int) pow(10, lenX) ;
            continue;
        }

        // 如果相等,继续判断 x, 2x, 3x, 4x, 5x, 6x 是否包含相同的数字

        // 获取 x 的所有数字
        std::vector<int> digitsX = getDigitsSorted(x);

        bool bHasSameDigits = true;
        for(int i = 2; i <= 6; i++){
            // 获取 i*x 的所有数字
            std::vector<int> digitsIX= getDigitsSorted(i*x);
            if( ! hasSameDigits(digitsX, digitsIX)){
                bHasSameDigits = false;
                break;
            }
        }

        // 找到了一个满足条件的解
        if(bHasSameDigits){
            printf("find answer: %d, %d, %d, %d, %d, %d\n", x, 2*x,3*x, 4*x, 5*x, 6*x);
            return 0;
        }

        // 继续查找下一个数
        x++;
    }

    return 0;
}

Golang #

package main

import (
	"fmt"
	"math"
	"sort"
)

func getDigitsSorted(n int) []int {
	var digits []int
	for n > 0 {
		digits = append(digits, n%10)
		n /= 10
	}

	sort.Slice(digits, func(i, j int) bool {
		return digits[i] < digits[j]
	})

	return digits
}

func hasSameDigits(v1, v2 []int) bool {

	if len(v1) != len(v2) {
		return false
	}

	for i := 0; i < len(v1); i++ {
		if v1[i] != v2[i] {
			return false
		}
	}

	return true
}

func main() {
	x := 11
	for {
		// 判断 x 和 6x 的位数是否相等
		lenX := len(fmt.Sprintf("%d", x))
		len6X := len(fmt.Sprintf("%d", 6*x))

		// 如果不相等,在 x 位数不变的情况下,随着 x 的增大,两者更不可能相等
		// 所以,此时需要给 x 增加位数
		// 如, x = 17,6x = 102,此时 18~99 都可以直接跳过了,直接跳到下一个位数的起始点 x = 100,再继续处理
		if len6X > lenX {
			x = int(math.Pow(10, float64(lenX)))
			continue
		}

		// 如果相等,继续判断 x, 2x, 3x, 4x, 5x, 6x 是否包含相同的数字

		// 获取 x 的所有数字
		digitsX := getDigitsSorted(x)

		bHasSameDigits := true
		for i := 2; i <= 6; i++ {
			// 获取 i*x 的所有数字
			digitsIX := getDigitsSorted(i * x)

			if !hasSameDigits(digitsX, digitsIX) {
				bHasSameDigits = false
				break
			}
		}

		// 找到了一个满足条件的解
		if bHasSameDigits {
			fmt.Printf("find answer: %d, %d, %d, %d, %d, %d\n", x, 2*x, 3*x, 4*x, 5*x, 6*x)
			return
		}

		// 继续查找下一个数
		x++
	}
}

Python #

x = int(11)

while True:
    # 判断 x 和 6x 的位数是否相等
    lenX = len(str(x))
    len6X = len(str(6*x))

    # 如果不相等,在 x 位数不变的情况下,随着 x 的增大,两者更不可能相等
    # 所以,此时需要给 x 增加位数
    # 如, x = 17,6x = 102,此时 18~99 都可以直接跳过了,直接跳到下一个位数的起始点 x = 100,再继续处理
    if len6X > lenX :
        x = 10**lenX
        continue
    
    # 如果相等,继续判断 x, 2x, 3x, 4x, 5x, 6x 是否包含相同的数字
    # 获取 x 的所有数字
    digitsX = list(str(x))
    digitsX.sort()

    bHasSameDigits = True
    for i in range(1,7):
        # 获取 i*x 的所有数字
        digitsIX = list(str(i*x))
        digitsIX.sort()
        
        if digitsX != digitsIX :
            bHasSameDigits = False
            break

    # 找到了一个满足条件的解
    if bHasSameDigits :
        print("find answer: ", x, 2*x, 3*x, 4*x, 5*x, 6*x)
        exit(0)
    
    # 继续查找下一个数
    x = x + 1

答案 #

142857

find answer: 142857, 285714, 428571, 571428, 714285, 857142