Codewars division Kata using Javascript is producing results that are not divisble by 6

Question

I am trying to solve this Kata from Codewars: https://www.codewars.com/kata/simple-fun-number-258-is-divisible-by-6/train/javascript

The idea is that a number (expressed as a string) with one digit replaced with *, such as "1047*66", will be inserted into a function. You must return an array in which the values are the original number with the * replaced with any digit that will produce a number divisive by 6. So given "1*0", the correct resulting array should be [120, 150, 180].

I have some code that is producing some correct results but erroring for others, and I can't figure out why. Here's the code:

function isDivisibleBy6(s) {

 var results = [];

 for(i=0;i<10;i++) {

  var string = i.toString(); // Convert i to string, ready to be inserted into s
  var array = Array.from(s); // Make an array from s    
  var index = array.indexOf("*"); // Find where * is in the array of s
  array[index] = string; // Replace * with the string of i

  var number = array.join(""); // Join all indexes of the s array back together. Now we should have 
                               // a single number expressed as a string, with * replaced with i

  parseInt(number, 10); // Convert the string to an integer

  if((number % 6) == 0) {
  results.push(number);  
  } // If the integer is divisible by 6, add the integer into the results array

}
return(results);
};

This code works with the above example and generally with all smaller numbers. But it is producing errors for larger numbers. For example, when s is "29070521868839*57", the output should be []. However, I am getting ['29070521868839257', '29070521868839557', '29070521868839857']. I can't figure out where this would be going wrong. Is anyone able to help?

Answer 1

Sum of all digits is divisible by three and the last digit is divisible by two.

An approach:

• Get the index of the star.
• Get left and right string beside of the star.
• Return early if the last digit is not divisible by two.
• Take the sum of all digits.
• Finally create an array with missing digits:
  • Start loop from either zero (sum has no rest with three) or take the delta of three and the rest (because you want a number which is divisible by three).
  • Go while value is smaller then ten.
  • Increase the value either by 3 or by 6, if the index of the star is the last character.
  • Take left, value and right part for pushing to the result set.
• Return result.

function get6(s) {
    var index = s.indexOf('*'),
        left = s.slice(0, index),
        right = s.slice(index + 1),
        result = [],
        sum = 0,
        i, step;

    if (s[s.length - 1] % 2) return [];

    for (i = 0; i < s.length; i++) if (i !== index) sum += +s[i];
   
    i = sum % 3 && 3 - sum % 3;
    step = s.length - 1 === index ? 6 : 3;

    for (; i < 10; i += step) result.push(left + i + right);

    return result;
}

console.log(get6("*"));   // ["0", "6"]
console.log(get6("10*")); // ["102", "108"]
console.log(get6("1*0")); // ["120", "150", "180"]
console.log(get6("*1"));  // []
console.log(get6("1234567890123456789012345678*0")); // ["123456789012345678901234567800","123456789012345678901234567830","123456789012345678901234567860","123456789012345678901234567890"]

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

The problem is that these numbers are larger than the Number.MAX_SAFE_INTEGER - the point when JavaScript numbers break down in terms of reliability:

var num = 29070521868839257;
console.log(num > Number.MAX_SAFE_INTEGER);
console.log(num % 6);
console.log(num)

The last log shows that the num actually has a different value than what we gave it. This is because 29070521868839257 simply cannot be represented by a JavaScript number, hence you get the closest possible value that can be represented and that's 29070521868839256.

So, after some point in numbers, all mathematical operations become unreliable as the very numbers are imprecise.

What you can do instead is ignore treating this whole as a number - treat it as a string and only apply the principles of divisibility. This makes the task vastly easier.

For a number to be divisible by 6 it has to cover two criteria:

• it has to be divisible by 2.
  • to verify this, you can just get the very smallest digit and check if it's divisible by 2. For example in 29070521868839257 if we take 7, and check 7 % 2, we get 1 which means that it's odd. We don't need to consider the whole number.
• it has to be divisible by 3.
  • to verify this, you can sum each of the digits and see if that sum is divisible by 3. If we sum all the digits in 29070521868839257 we get 2 + 9 + 0 + 7 + 0 + 5 + 2 + 1 + 8 + 6 + 8 + 8 + 3 + 9 + 2 + 5 + 7 = 82 which is not divisible by 3. If in doubt, we can sum the digits again, since the rule can be applied to any number with more than two digits: 8 + 2 = 10 and 1 + 0 = 1. That is still not divisible by 3.

So, if we apply these we can get something like:

function isDivisibleBy6(s) {
  return isDivisibleBy2(s) && isDivisibleBy3(s);
};

function isDivisibleBy2(s) {
  var lastDigit = Number(s.slice(-1));
  
  return (lastDigit % 2) === 0;
}

function isDivisibleBy3(s) {
  var digits = s.split("")
    .map(Number);
    
  var sum = digits.reduce(function(a, b) {
    return a + b
  });
  
  return (sum % 3) === 0;
}

console.log(isDivisibleBy6("29070521868839257"));
console.log(isDivisibleBy6("29070521868839256"));

These can even be recursively defined true to the nature of these rules:

function isDivisibleBy6(s) {
  return isDivisibleBy2(s) && isDivisibleBy3(s);
};

function isDivisibleBy2(s) {
  if (s.length === 0) {
    return false;
  }
  
  if (s.length > 1) {
    return isDivisibleBy2(s.slice(-1));
  }
    
  var lastDigit = Number(s);
  return (lastDigit % 2) === 0;
}

function isDivisibleBy3(s) {
  if (s.length === 0) { 
    return false;
  }
  
  if (s.length > 1) {
    var digits = s.split("")
      .map(Number);
    
    var sum = digits.reduce(function(a, b) {
      return a + b
    });
    
    return isDivisibleBy3(String(sum));
  }
  
  var num = Number(s);
  return (num % 3) === 0;
}

console.log(isDivisibleBy6("29070521868839257"));
console.log(isDivisibleBy6("29070521868839256"));

This is purely to demonstrate the rules of division and how they can be applied to strings. You have to create numbers that will be divisible by 6 and to do that, you have to replace an asterisk. The easiest way to do it is like you did - generate all possibilities (e.g., 1*0 will be 100, 110, 120, 130, 140, 150, 160, 170, 180, 190) and then filter out whatever is not divisible by 6:

function isDivisibleBy6(s) {
  var allDigits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
  
  var allPossibleNumbers = allDigits.map(function(digit) {
    return s.replace("*", digit);
  });
  
  var numbersDibisibleBySix = allPossibleNumbers.filter(function(s) {
    return isDivisibleBy2(s) && isDivisibleBy3(s);
  })
  
  return numbersDibisibleBySix;
};

function isDivisibleBy2(s) {
  var lastDigit = Number(s.slice(-1));
  
  return (lastDigit % 2) === 0;
}

function isDivisibleBy3(s) {
  var digits = s.split("")
    .map(Number);
    
  var sum = digits.reduce(function(a, b) {
    return a + b
  });
  
  return (sum % 3) === 0;
}

console.log(isDivisibleBy6("29070521868839*57"));
console.log(isDivisibleBy6("29070521868839*56"));

As a last note, this can be written more concisely by removing intermediate values and using arrow functions:

function isDivisibleBy6(s) {
  return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    .map(digit => s.replace("*", digit))
    .filter(s => isDivisibleBy2(s) && isDivisibleBy3(s));
};

const isDivisibleBy2 = s => Number(s.slice(-1)) % 2 === 0;

const isDivisibleBy3 = s => s.split("")
    .map(Number)
    .reduce((a, b) => a + b) % 3 === 0

console.log(isDivisibleBy6("29070521868839*57"));
console.log(isDivisibleBy6("29070521868839*56"));

Answer 3

The problem is with:

parseInt(number, 10); 

You can check and see that when number is large enough, this result converted back to string is not equal to the original value of number, due to the limit on floating point precision.

This challenge can be solved without having to convert the given string to number. Instead use a property of numbers that are multiples of 6. They are multiples of 3 and even. Multiples of 3 have the property that the sum of the digits (in decimal representation) are also multiples of 3.

So start by checking that the last digit is not 1, 3, 5, 7, or 9, because in that case there is no solution.

Otherwise, sum up the digits (ignore the asterisk). Determine which value you still need to add to that sum to get to a multiple of 3. This will be 0, 1 or 2. If the asterisk is not at the far right, produce solutions with this digit, and 3, 6, 9 added to it (until you get double digits).

If the asterisk is at the far right, you can do the same, but you must make sure that you exclude odd digits in that position.

If you are desperate, here is a solution. But I hope you can make it work yourself.

function isDivisibleBy6(s) {
    // If last digit is odd, it can never be divisable by 6
    if ("13579".includes(s[s.length-1])) return [];
    let [left, right] = s.split("*");

    // Calculate the sum of the digits (ignore the asterisk)
    let sum = 0;
    for (let ch of s) sum += +ch || 0;

    // What value remains to be added to make the digit-sum a multiple of 3?
    sum = (3 - sum%3) % 3;
    
    // When asterisk in last position, then solution digit are 6 apart, otherwise 3
    let mod = right.length ? 3 : 6;
    if (mod === 6 && sum % 2) sum += 3; // Don't allow odd digit at last position

    // Build the solutions, by injecting the found digit values
    let result = [];
    for (; sum < 10; sum += mod) result.push(left + sum + right);
    return result;
}

// Demo
console.log(isDivisibleBy6("1234567890123456789012345678*0"));

BigInt

There is also another way to get around the floating point precision problem: use BigInt instead of floating point. However, BigInt is not supported on CodeWars, at least not in that specific Kata, where the available version of Node goes up to 8.1.3, while BigInt was introduced only in Node 10.

function isDivisibleBy6(s) {
    let [left, right] = s.split("*");
    let result = [];
    for (let i = 0; i < 10; i++) {
        let k = BigInt(left + i + right);
        if (k % 6n === 0n) result.push(k.toString());
    }
    return result;
}

// Demo
console.log(isDivisibleBy6("1234567890123456789012345678*0"));

This would anyway feel like "cheating" (if it were accepted), as it's clearly not the purpose of the Kata.

Answer 4

As mentioned, the values you are using are above the maximum integer value and therefore unsafe, please see the docmentation about this over here Number.MAX_SAFE_INTEGER. You can use BigInt(string) to use larger values.

Answer 5

Thanks for all the responses. I have now created successful code!

function isDivisibleBy6(s) {

 var results = [];

 for(i=0;i<10;i++) {

  var string = i.toString();
  var array = Array.from(s);
  var index = array.indexOf("*");
  array[index] = string;

  var div2 = 0;
  var div3 = 0;

  if(parseInt((array[array.length-1]),10) % 2 == 0) {
  div2 = 1;
  }

  var numarray = array.map((x) => parseInt(x));

  if(numarray.reduce(function myFunc(acc, value) {return acc+value}) % 3 == 0) {      
  div3 = 1;
  }

  if(div2 == 1 && div3 == 1) {
   results.push(array.join(""));
  }
}
return(results);
};

I know this could be factored down quite a bit by merging the if expressions together, but I like to see things split out so that when I look back over previous solutions my thought process is clearer.

Thanks again for all the help!