数字分组求偶数和

问题描述

小M面对一组从 1 到 9 的数字，这些数字被分成多个小组，并从每个小组中选择一个数字组成一个新的数。目标是使得这个新数的各位数字之和为偶数。任务是计算出有多少种不同的分组和选择方法可以达到这一目标。

要求:

numbers: 一个由多个整数字符串组成的列表，每个字符串可以视为一个数字组。小M需要从每个数字组中选择一个数字。

例如: 对于 [123, 456, 789]，14 个符合条件的数为: 147 149 158 167 169 248 257 259 268 347 349 358 367 369。

测试样例

样例1：

输入：numbers = [123, 456, 789]
输出：14

样例2：

输入：numbers = [111, 222, 333]
输出：0

样例3：

输入：numbers = [123, 456, 789, 111, 222, 333]
输出：14

解题思路

初始化一个变量 count，用于存储所有数字的和。初始值为 0。

遍历数组中的每个数字，将其转换为字符串，并逐个字符地遍历。

对于每个字符，将其转换为数字，并加到 count 中。

最后，返回 count 的值。

代码实现

Cangjie

func solution(numbers: Array<Int64>) {
    var count = 0
    func backtrack(index: Int64, current_sum: Int64): Unit {
        if (index == numbers.size) {
            if (current_sum % 2 == 0) {
                count++
            }
            return;
        }
        let group = numbers[index].toString().toRuneArray()
        for (digit in group) {
            let selectedDigit = Int64(UInt32(digit) - 48)
            backtrack(index + 1, current_sum + selectedDigit)
        }
    }
    backtrack(0, 0)
    count
}

main() {
    println(solution([123, 456, 789]) == 14)
    println(solution([123456789]) == 4)
    println(solution([14329, 7568]) == 10)
}

Rust

fn solution(numbers: Vec<i32>) -> i32 {
    let mut count = 0;
    fn backtrack(index: usize, 
        current_sum: i32, 
        numbers: &Vec<i32>, 
        count: &mut i32) {
        if index == numbers.len() {
            if current_sum % 2 == 0 { *count += 1 }
            return;
        }
        let group = numbers[index].to_string();
        for digit in group.chars() {
            let digit = digit.to_digit(10).unwrap() as i32;
            backtrack(index + 1,
                current_sum + digit, 
                numbers, 
                count);
        }
    }
    backtrack(0, 0, &numbers, &mut count);
    count
}

 fn main() {
    println!("{}", solution(vec![123, 456, 789]) == 14);
    println!("{}", solution(vec![123456789]) == 4);
    println!("{}", solution(vec![14329, 7568]) == 10);
 }

Python

def solution(numbers):
    count = 0

    # back tracking function
    def backtrack(index, currentSum):
        if index == len(numbers):
            if currentSum % 2 == 0:
                nonlocal count
                count += 1
            return

        group = str(numbers[index])
        for digit in group:
            digit = int(digit)
            backtrack(index + 1, currentSum + digit)
    
    backtrack(0, 0)
    return count

print(solution([123, 456, 789]) == 14)
print(solution([123456789]) == 4)
print(solution([14329, 7568]) == 10)

JavaScript

function solution(numbers) {
    let count = 0;
    function backtrack(index, currentSum) {
        if (index === numbers.length) {
            if (currentSum % 2 === 0) {
                count++;
            }
            return;
        }
        const group = numbers[index].toString();
        for (const digit of group) {
            const selectedDigit = parseInt(digit);
            backtrack(index + 1, currentSum + selectedDigit);
        }
    }
    backtrack(0, 0);
    return count;
}

console.log(solution([123, 456, 789]) === 14);
console.log(solution([123456789]) === 4);
console.log(solution([14329, 7568]) === 10);

复杂度分析

时间复杂度：O(n^2)

空间复杂度：O(n)

仓颉编程语言