032. Pandigital Products [두 수의 곱이 Pandigital이 되는 수 찾기]

​문제 (English)

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 \times 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.

 

Answer: 45228

문제 분석

---

$39 \times 186 = 7254$ 처럼, 어떤 두 수의 곱을 했을 때, 어떤 두 수와 곱의 결괏값 모두의 각 자릿수를 봤을 때, 1에서 n까지 연속된 수이면 Pandigital이라고 하는데, 1~9까지의 모든 수가 들어가는 Pandigital이 되는 두 수의 곱을 찾아서 모두 더하라는 문제.

 

곱하는 두 수를 a, b라고 하고, 그 곱 결괏값을 c라고하면, 각 수의 자릿수 크기를 합한 게 9가 돼야 하고, 모든 자릿수가 중복이 없어야 한다. 

이러한 두 수를 적절히 찾아서, 그 곱을 더하면 된다.

 

그렇다면, 두 수를 찾을 때, 어떻게 최소 범위에서 찾게 할것인가? 두 수와 그 곱한 값에 대해 Pandigital이 되는지를 어떻게 효율적으로 체크할 것인가? 이러한 것이 문제 풀이에 핵심이 되겠다.

 

또한, 9개의 수에서 두 수를 뽑아내게하는 조합방식을 써서 구현하는 게 나을 것인지, 아니면 1~n까지의 수에 대해서 모두 검사하게 하는 게 나은지도 판단하면 좋겠다.

풀이 1 

---

두 수의 곱을 했을 때 몇 자리의 수가 나오는지를 조사해보자. 예를 들어 2자리 $\times$ 2자리의 수를 곱했을 때 몇 자리의 수가 나오는지를 조사해 보는 것이다.

 

이 경우, 2자리 수의 최솟값은 $10^{2-1}=10$이다. 최댓값은 $10^{2}-1=99$ 이고, 최솟값끼리 곱하면 100 -> 3자리, 최댓값까지 곱하면 9801 -> 4자리가 된다. 

이렇게 엑셀에서 조사해본게 아래 표이다.

 

표의 윗부분은 최솟값끼리, 그리고 최댓값끼리 곱한 값이고, 아래 표는 이러한 결괏값에 따라 나오는 전체 자릿수이다. 전체 자릿수라 함은 L(a) + L(b) + L(c)를 한 것으로, 곱한 두 수와 그 결괏값의 자릿수를 모두 더한 것.

 

이렇게 보년 전체 4자리 수가 되려면, 1 자릿수와 1자리 수의 곱인 경우만 4자리 수가 된다. 

전체 5자리가 되려면 1자리 $\times$ 2자리

전체 6자리가 되려면 1자리 $\times$ 2자리

 

정리해 보면, 

전체 자릿수가 4인 경우는 (1자리 $\times$ 1자리)이다. 그럼 이 경우, 그 한 자릿수에서 최소와 최대로 검사할 대상은 어떻게 될까? 

먼저 최솟값부터 보면, 1의 경우는 안된다. 왜냐면 1에다가 4를 곱해도 1 자릿수가 나오기 때문. 즉, 1자리 $\times$ 1자리 = 2자리가 나오는 형태라야 하는데, a가 1이면 b에 1~4까지의 어떤 값을 넣어도 c가 2자리가 안되기 때문. 여기서 자릿수가 4이기 때문에 가용한 수는 1~4이다.

같은 논리로 2도 안된다. $2 \times 4=8$로, 결과가 2자릿수가 안되기 때문. 

3부터는 된다. 그리고, 실제로 4자리가 되는 두 수의 곱은 $3 \times 4 = 12$이다. 

 

5자리에 대해서는 (1자리 \times 2자리)의 경우인데, 최솟값은 2이고, 최댓값은 54이다. 가용한 수가 1~5이기 때문이고, 1의 경우는 1에 어떠한 값 b를 곱해도 b가 되기 때문에 중복이 발생해서 Pandigital이 안된다.

6자리에 대해서는 (1자리 \times 2자리)인데, 가용한 수가 1~6까지이기에 두 자릿수 최댓값은 65이다. 

7~9자리까지 같은 논리

 

이제, 9자리의 Pandigital 되는 수를 찾으려면, 2에서 9876까지의 수에 대해서 조사하면 되겠다.

물론, 더 세밀하게 하면 아래와 같이 세분화시켜서 범위를 줄일 수 있는데, 마이너 하다.

• 2자리 $\times$ 3자리의 경우: 
  • a 범위: 12 ~ 98
  • b의 범위: 123 ~ 987
• 1자리 $\times$ 4자리의 경우:
  • a 범위: 2  ~ 9
  • b 범위: 1234 ~ 9876

HackerRank의 경우 9자리에 고정된 것이 아니라 4~9 사이의 n이 주어졌을 때, Pandigital이 되는 결과곱의 합을 구하는 것이기에, 불특정 n에 대해 조사할 범위 최솟값과 최댓값을 리턴하는 함수를 만들어 사용하자.

#[cfg(test)]
// return (min, max) value for the given n digit
// n: 4..=9
fn get_min_max(n:usize)  -> (usize, usize) {
    let min_val:usize; let max_val:usize;

    match n {
        4 => { min_val = 3; max_val = 4; },
        5 => { min_val = 2; max_val = 54; },
        6 => { min_val = 2; max_val = 65; },
        7 => { min_val = 2; max_val = 765; },
        8 => { min_val = 2; max_val = 876; },
        9 => { min_val = 2; max_val = 9876; },
        _ => { min_val = 0; max_val = 0; },
    }
    return (min_val, max_val);
}

 

get_min_max 함수로부터 조사할 범위를 알아낸 후, 이 범위에서 $a \times b = c$를 조사하면서 Pandigital이 되는 값을 찾아내면 된다.

#[cfg(test)]
fn answer(n:usize) -> usize {
    use std::collections::HashSet;

    let mut set:HashSet<usize> = HashSet::new();
    let (start, end) = get_min_max(n);
    for a in start..=end {
        for b in start..=end{
            if a >= b {continue;}
            let c = a * b;
            if is_pandital(n, a, b, c) {
                //println!("a={},b={},c={}",a,b,c);
                set.insert(c);
            }
        }
    }
    return set.into_iter().sum();
}

코드를 보면,

• 항상 a < b 인 경우만 고려했다. $a \times b = b \times a$가 되는 경우의 수를 배제하기 위한 트릭이다.
• is_pandigital 함수를 따로 만들었다. 아래 부분에 설명
• $18 \times 297 = 5346$과 $27 \times 198 = 5346$으로, a와 b의 값이 달라도 c가 같은 경우가 있다. 문제의 조건에서, 이처럼 c가 중복된 경우 한 개만 더하라고 했기에, c를 Hashset에 저장해서 중복이 생기지 않게 했다.

is_pandigital 함수는 $a \times b = c$에서 a, b, c의 값들에 의해 Pandigial이 되는지 아닌지를 판별하게 하는 함수이다. 

여러 가지 구현 방법을 생각할 수 있겠다. 

• str(n) = str(a) || str(b) || str(c)처럼, 각 숫자를 문자열로 바꿔서 결합한 후, L(n)==9이고, 중복된 문자가 없는지를 확인할 수도 있겠고,
• 크기 n+1인 배열 v를 만들고, a, b, c의 각 자릿수에 대해 v의 각 자릿수를 1로 체크하면서, v의 모든 값이 단 한 번만 1로 체크되는지 확인할 수도 있겠다.  

여기서는 두 번째 방법을 사용했다.

#[cfg(test)]
//check whether axb=c is pandital or not between 1..=n
fn is_pandital(n:usize, mut a:usize, mut b:usize, mut c:usize) -> bool{
    let mut v:Vec<usize> = vec![0;n+1]; v[0]=1;
    let mut cnt = 0;

    while a > 0 {
        let k = a % 10;
        if k > n || v[k] == 1 {return false;}
        v[k] = 1; cnt += 1;   a /= 10;
    }

    while b > 0 {
        let k = b % 10;
        if k > n || v[k] == 1 {return false;}
        v[k] = 1; cnt += 1; b /= 10;
    }

    while c > 0 {
        let k = c % 10;
        if k > n || v[k] == 1 {return false;}
        v[k] = 1; cnt += 1; c /= 10;
    }

    //no need to check all v[i]==1 but just checking cnt is enough
    if cnt == n {return true;}
    else {return false;}
}

 

이 코드로 HackerRank도 통과 가능하다.

 

총평

---

수에 대한 조합을 생각해보게 하는 문제이다. 굳이 조합 코드를 만들어서 사용할 수도 있으나, 조사할 범위만 잘 조정하면, 연속된 십진수 값으로의 조합에 의해 쉽게 문제를 풀 수 있다.

그러기 위해서는, 과연 2자리 $\times$ 2자리를 했을 때, 몇 자리의 수가 나올 수 있을지 등에 대한 생각을 할 수 있어야 하겠다.

 

아래 전체 소스코드에는 n 자리 수에 대한 조합(Permutation)을 생성해 내는 코드가 들어 있다. 이 문제에서 실제 사용하지는 않았고, 처음에 이러한 조합을 이용해서 문제를 풀까 하다가, 그러지 않았다. 

 

전체 소스코드

---

p32.rs 

#[test]
fn test(){    
    // assert_eq!(true, is_pandital(4, 3, 4, 12));
    // assert_eq!(false, is_pandital(4, 4, 5, 20));

    assert_eq!(12,answer(4));
    assert_eq!(45228,answer(9));
}

#[cfg(test)]
fn answer(n:usize) -> usize {
    use std::collections::HashSet;

    let mut set:HashSet<usize> = HashSet::new();
    let (start, end) = get_min_max(n);
    for a in start..=end {
        for b in start..=end{
            if a >= b {continue;}
            let c = a * b;
            if is_pandital(n, a, b, c) {
                //println!("a={},b={},c={}",a,b,c);
                set.insert(c);
            }
        }
    }
    return set.into_iter().sum();
}

#[cfg(test)]
// return (min, max) value for the given n digit
// n: 4..=9
fn get_min_max(n:usize)  -> (usize, usize) {
    let min_val:usize; let max_val:usize;

    match n {
        4 => { min_val = 3; max_val = 4; },
        5 => { min_val = 2; max_val = 54; },
        6 => { min_val = 2; max_val = 65; },
        7 => { min_val = 2; max_val = 765; },
        8 => { min_val = 2; max_val = 876; },
        9 => { min_val = 2; max_val = 9876; },
        _ => { min_val = 0; max_val = 0; },
    }
    return (min_val, max_val);
}

#[cfg(test)]
//check whether axb=c is pandital or not between 1..=n
fn is_pandital(n:usize, mut a:usize, mut b:usize, mut c:usize) -> bool{
    let mut v:Vec<usize> = vec![0;n+1]; v[0]=1;
    let mut cnt = 0;

    while a > 0 {
        let k = a % 10;
        if k > n || v[k] == 1 {return false;}
        v[k] = 1; cnt += 1;   a /= 10;
    }

    while b > 0 {
        let k = b % 10;
        if k > n || v[k] == 1 {return false;}
        v[k] = 1; cnt += 1; b /= 10;
    }

    while c > 0 {
        let k = c % 10;
        if k > n || v[k] == 1 {return false;}
        v[k] = 1; cnt += 1; c /= 10;
    }

    //no need to check all v[i]==1 but just checking cnt is enough
    if cnt == n {return true;}
    else {return false;}
}



//-------------------------------
//
#[test]
fn test5(){
    let mut a = vec![1,2,3];
    println!("{:?}",a);
    while next(&mut a) {
        println!("{:?}",a);
    }

    // [1, 2, 3]
    // [1, 3, 2]
    // [2, 1, 3]
    // [2, 3, 1]
    // [3, 1, 2]
    // [3, 2, 1]
}

#[cfg(test)]
fn next(a:&mut Vec<usize>) -> bool {
    let mut i:usize;  let mut j:usize;

    //1. find max i, where a[i-1]<a[i]
    i = a.len()-1;
    while i>0 && a[i-1] >= a[i] {i -= 1;}
    if i==0 {return false;}

    //2. find max j, where i<=j, a[i-1]<a[j]
    j = a.len()-1;
    while a[i-1] >= a[j] {j -= 1;}

    //3. swap(a[i-1], a[j])
    let tmp = a[i-1];
    a[i-1]=a[j]; a[j]=tmp;

    //4. reverse a to {a[n-1]...a[i]}
    j=a.len()-1;
    while i < j {
        let tmp = a[i]; a[i]=a[j]; a[j]=tmp;
        i += 1; j -= 1;
    }

    return true;
}

 

끝