hai5nguy · February 9, 2020 00:04
diff --git a/all-evens.js b/all-evens.js

 /**
 * You can brute force and increment/decrement the given number until you find a valid-all-even-digits
 * number, but the time complexity would be O(n) where n is value of the number.  Instead, you
 * can validate each digit starting with the highest power to come up with the nearest valid number.
 * Since you can make a number even by going up or down, both paths have to be considered.
 * 
 * For example, take 567;
 * 
 * It won't matter what you do with '67' because '5' will always be invalid.  So you have to make it even.
 * 
 * Going up: 5 -> 6     valid!
 * Going down: 5 -> 4   valid!
 * 
 * Then you have to handle the rest, the '67', 
 * 
 * if you are going up: 67 -> 00 because that's the nearest valid higher value i.e. 600
 * if you are going down: 67 -> 88 because that's the nearest valid LOWER value i.e. 488
 * 
 * Now you have the lower and upper, the min of those two from the original number is the minimum clicks
 * the user has to make.
 * 
 * The time complexity of this solution is O(d) where d is the number of digits.
 * 
 */

 findMinClicks(42)  		// 0
 findMinClicks(2)		// 0
 findMinClicks(3)		// 1
 findMinClicks(1016) 	// 128
 findMinClicks(555)		// 45
 findMinClicks(7771)		// 229
 findMinClicks(8882) 	// 0

 function findMinClicks(number) {
    const upper = findNearestNumberWithEvenDigits(number, +1, '0')
    const lower = findNearestNumberWithEvenDigits(number, -1, '8')
    const min = Math.min(upper - number, number - lower)
    console.log(number, '  upper:', upper, ' lower:', lower, ' -> ', min)
 }

 function findNearestNumberWithEvenDigits(number, direction, fillDigit) {
 	let result = [];
    let num = String(number).split('')
  
    do {
        let [first, ...rest] = num; // first is the highest power digit
    
        if (first % 2 === 0) {      // even - the digit is ok, push it to the result
            result.push(first)
        } else {                    // odd - digit is not ok, increment or decrement to make it even.
            result.push(Number(first) + direction)
            rest.fill(fillDigit)    // fill the rest (insignficant digits) with '0' or '8'
            result = [...result, ...rest] 
            break;                  // we are done, no need to continue;
        }
        
        num = rest
    } while (num.length)
  
    return Number.parseInt(result.join(''))
 }

	/**
	* You can brute force and increment/decrement the given number until you find a valid-all-even-digits
	* number, but the time complexity would be O(n) where n is value of the number. Instead, you
	* can validate each digit starting with the highest power to come up with the nearest valid number.
	* Since you can make a number even by going up or down, both paths have to be considered.
	*
	* For example, take 567;
	*
	* It won't matter what you do with '67' because '5' will always be invalid. So you have to make it even.
	*
	* Going up: 5 -> 6 valid!
	* Going down: 5 -> 4 valid!
	*
	* Then you have to handle the rest, the '67',
	*
	* if you are going up: 67 -> 00 because that's the nearest valid higher value i.e. 600
	* if you are going down: 67 -> 88 because that's the nearest valid LOWER value i.e. 488
	*
	* Now you have the lower and upper, the min of those two from the original number is the minimum clicks
	* the user has to make.
	*
	* The time complexity of this solution is O(d) where d is the number of digits.
	*
	*/

	findMinClicks(42) // 0
	findMinClicks(2) // 0
	findMinClicks(3) // 1
	findMinClicks(1016) // 128
	findMinClicks(555) // 45
	findMinClicks(7771) // 229
	findMinClicks(8882) // 0

	function findMinClicks(number) {
	const upper = findNearestNumberWithEvenDigits(number, +1, '0')
	const lower = findNearestNumberWithEvenDigits(number, -1, '8')
	const min = Math.min(upper - number, number - lower)
	console.log(number, ' upper:', upper, ' lower:', lower, ' -> ', min)
	}

	function findNearestNumberWithEvenDigits(number, direction, fillDigit) {
	let result = [];
	let num = String(number).split('')

	do {
	let [first, ...rest] = num; // first is the highest power digit

	if (first % 2 === 0) { // even - the digit is ok, push it to the result
	result.push(first)
	} else { // odd - digit is not ok, increment or decrement to make it even.
	result.push(Number(first) + direction)
	rest.fill(fillDigit) // fill the rest (insignficant digits) with '0' or '8'
	result = [...result, ...rest]
	break; // we are done, no need to continue;
	}

	num = rest
	} while (num.length)

	return Number.parseInt(result.join(''))
	}