Нахождение точки соединения двух последовательностей

Question

Мы рассматриваем последовательность чисел, в которой за номером следует то же число плюс сумма его цифр. Например, за 34 следует 41 (так как 41 = 34 + (3 + 4)), за которым следует 46 (46 = 41 + (4 + 1)). Последовательность будет 34 41 46 56 67 ....

Две последовательности, которые начинаются с разных номеров, могут объединяться в данной точке, например, последовательность, начинающаяся с 471, и последовательность, начинающаяся с 480, делят число 519

Реализация функции, которая принимает старт точки двух последовательностей, а затем возвращает точку соединения этих последовательностей.

Мой ответ:

function computeJoinPoint(s1, s2) {
  const digitSum = num => String(num).split('').reduce((a, b) => parseInt(a) + parseInt(b))
  while (s1 !== s2) {
   s1 += digitSum(s1)
   s2 += digitSum(s2)
  }
  return s1

}

Я проверил свое решение с аргументами (471, 480) и сработало, однако, один из тестовых случаев говорит, что аргументы 57, 78, и программа ожидает некоторой точки соединения, но моя реализация не дает никакого решения.

В задаче приведены следующие ограничения:

• Указанные последовательности всегда объединяются
• 0 <точка соединения <20000000 </li>
• 0

что-то не так с моей реализацией? Есть ли математический способ определить, сходятся ли последовательности, начинающиеся с 57, 78, в какой-то момент?

Answer 1

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

Один из способов исправить это - «запомнить» каждое посещенное число:

function computeJoinPoint(s1, s2) {
  console.log(s1, s2);
  const digitSum = num => {
    return String(num).split('').reduce((a, b) => parseInt(a) + parseInt(b), 0);
  }
  const visited = {};
  let maxIterations = 1000; // so the browser won't hang if you try something weird
  while (s1 !== s2) {
    if (!maxIterations--) {
      throw new Error('giving up');
    }
    s1 += digitSum(s1);
    s2 += digitSum(s2);
    console.log(s1, s2);
    if (visited[s1] || visited[s2]) {
      return visited[s1] || visited[s2];
    }
    visited[s1] = s1;
    visited[s2] = s2;
  }
  return s1;
}
console.log('join point:', computeJoinPoint(57, 78));

Другой способ заключается в обновлении только меньшего числа в каждой итерации:

function computeJoinPoint(s1, s2) {
  console.log(s1, s2);
  const digitSum = num => {
    return String(num).split('').reduce((a, b) => parseInt(a) + parseInt(b), 0);
  }
  let maxIterations = 1000; // so the browser won't hang if you try something weird
  while (true) {
    if (!maxIterations--) {
      throw new Error('giving up');
    }
    if (s1 < s2) {
      s1 += digitSum(s1);
      console.log(s1, s2);
    } else if (s1 > s2) {
      s2 += digitSum(s2);
      console.log(s1, s2);
    } else {
      return s1;
    }
  }
}
console.log('join point:', computeJoinPoint(57, 78));

Answer 2

// i am not allowed to comment, so i'll try to address Steven's question about the convergence here
// 1. if both numbers are evenly divisible by 9, there is a joint point (9, 27) -> 36
// 2. else if only one number is divisible by 9 , there is no joint point (6, 9) -> ?
// 3. else if the numbers' moduli with 3 are equal (4, 7)-> 107, or 
//    the sum of their moduli with 3 is 3 as in (4, 5) -> 620, there is a joint point
// 4. in all other cases there is no joint point
// in both cases that you have (57, 78) and (471, 480) the numbers are divisible by 3, and none of them is divible by 9
// so they both converge
// for case 1 it's easy to find the joint point, it's max(a, b) + sum of its digits
// for case 3 i have no idea where the joint point comes from
// there are joint points that are repeated for different a, b values: 107, 109, 111, 214, 620 etc but no obvious pattern
const sequencesConverge = (a, b) => {
	const [a3, a9, b3, b9] = [a % 3, a % 9, b % 3, b % 9];
	return (a9 === 0 && b9 === 0) || (a9 * b9 !== 0 && (a3 === b3 || a3 + b3 === 3));
}
console.log(sequencesConverge(57, 78));
console.log(sequencesConverge(471, 480));