количество подпоследовательностей, сумма которых делится на k - PullRequest
Новая
       6

количество подпоследовательностей, сумма которых делится на k

0 голосов
/ 05 января 2019

Я только что выполнил задачу по кодированию для компании и не смог решить эту проблему. Постановка проблемы выглядит так:

Учитывая массив целых чисел, найдите количество подпоследовательностей в массиве, сумма которого делится на k, где k - некоторое положительное целое число.

Например, для [4, 1, 3, 2] и k = 3 решение равно 5. [[3], [1, 2], [4,3,2], [4,2], [1,3,2]] - это подпоследовательности, сумма которых делится на k, то есть current_sum + nums[i] % k == 0, где nums[i] - текущий элемент в массив.

Я пытался решить эту проблему рекурсивно, однако я не смог пройти ни одного теста. Мой рекурсивный код был примерно таким: 

def kSum(nums, k):
    def kSum(cur_sum, i):
        if i == len(nums): return 0
        sol = 1 if (cur_sum + nums[i]) % k == 0 else 0
        return sol + kSum(cur_sum, i+1) + kSum(cur_sum + nums[i], i+1)
    return kSum(0, 0)

Что не так с этим рекурсивным подходом и как я могу его исправить? Меня не интересует итеративное решение, я просто хочу знать, почему это рекурсивное решение неверно и как я могу его исправить.

Ответы [ 3 ]

0 голосов
/ 05 января 2019

Вы уверены, что это не тематический тест? Например: 

[4, 1, 3, 2], k = 3

имеет 

4+2 = 6, 1+2=3, 3, 1+2+3=6, 4+2+3 = 9

Итак, ваша функция верна (она дает мне 5), и я не вижу серьезных проблем с вашей функцией.

0 голосов
/ 06 января 2019

Мне кажется, что ваше решение верное. Он достигает ответа, пробуя все подпоследовательности, которые имеют 2^n сложность. Мы могли бы сформулировать это рекурсивно в O(n*k) пространстве поиска, хотя это может быть более эффективным для таблицы. Пусть f(A, k, i, r) представляет, сколько подпоследовательностей оставляют остаток r, когда их сумма делится на k, с использованием элементов до A[i]. Тогда: 

function f(A, k, i=A.length-1, r=0){
  // A[i] leaves remainder r
  // when divided by k
  const c = A[i] % k == r ? 1 : 0;

  if (i == 0)
    return c;
  
  return c +  
    // All previous subsequences 
    // who's sum leaves remainder r
    // when divided by k
    f(A, k, i - 1, r) +

    // All previous subsequences who's
    // sum when combined with A[i]
    // leaves remainder r when
    // divided by k
    f(A, k, i - 1, (k + r - A[i]%k) % k);
}

console.log(f([1,2,1], 3));
console.log(f([2,3,5,8], 5));
console.log(f([4,1,3,2], 3));
console.log(f([3,3,3], 3));
0 голосов
/ 05 января 2019

Вот javascript-репродукция того, что вы написали с некоторыми журналами консоли, чтобы помочь объяснить его поведение. 

function kSum(nums, k) {
  let recursive_depth = 1;
  function _kSum(cur_sum, i) {
    recursive_depth++;
    
    if (i == nums.length) {
      recursive_depth--;
      return 0;
    }
    let sol = 0;
    if (((cur_sum + nums[i]) % k) === 0) {
      sol = 1;
      console.log(`Found valid sequence ending with ${nums[i]} with sum = ${cur_sum + nums[i]} with partial sum ${cur_sum} at depth ${recursive_depth}`);
    }
    const _kSum1 = _kSum(cur_sum, i+1);
    const _kSum2 = _kSum(cur_sum + nums[i], i+1);
    const res = sol + _kSum1 + _kSum2;
    
    recursive_depth--;
    return res; 
  }
  return _kSum(0, 0);
}

let arr = [4, 1, 3, 2], k = 3;
console.log(kSum(arr, k));

Я думаю, что этот код действительно дает правильный ответ. Я не свободно владею Python, но я мог бы случайно исправить ошибку в вашем коде, добавив скобки вокруг (cur_sum + nums[i]) % k

...