Interview Question
Front-end Software EngineersCountry: United States
This type of problem is typically known as Partition problem. The number of partitions of a number grows exponentially. I read somewhere that Its an NP-Complete problem. Here are few references that you can check to know more about it.
math.stackexchange.com/questions/217597/number-of-ways-to-write-n-as-a-sum-of-k-nonnegative-integers
en.wikipedia.org/wiki/Partition_%28number_theory%29#Intermediate_function
stackoverflow.com/questions/400794/generating-the-partitions-of-a-number#400810
Some of these links will provide you with the implementation in some lang. You can go through the math for wikipedia link.
function countSteps(n){
var counts = 0;
function partition(arr, last ,m){
var tempArr;
if(m > 1){
for(var i = last || 1; i <= m/2; i++){
tempArr = arr.slice(0);
if(m-i > i){
tempArr.push(i);
if(m-i > 1){
partition(tempArr.slice(0), i, m-i);
}
tempArr.push(m-i);
}else if(m-i == i){
tempArr.push(i);
tempArr.push(m-i);
}else{
return
}
}
}else{
tempArr = arr.slice(0);
tempArr.push(m);
}
if(tempArr){
counts += 1;
console.log(tempArr);
}
}
partition([], null, n);
return counts;
}
var all = [];
function findStep(n) {
if (n===1){
console.log(1);
} else {
_findIt(n, []);
}
all.sort();
var prev = [];
for(var i=0; i<all.length; i++){
var curr = all[i];
if (curr.join() == prev.join()){
all.splice(i,1);
i--;
} else {
prev = curr;
}
}
console.log(all);
console.log(all.length);
}
function getSum (arr){
return arr.reduce(function(a,b){
return a+b;
},0);
}
function _findIt(n, result){
var currentSum = getSum(result);
for(var i = 1; i <= n; i++){
var nextSum = currentSum + i;
if (nextSum === n){
result.push(i);
result.sort();
//console.log(result.join());
all.push(result);
return;
} else {
var newArray = result.slice(0);
newArray.push(i);
_findIt(n, newArray);
}
}
}
findStep(4)
I am not sure about the exact problem.
- Nitin Gupta January 28, 2014But from example it seems that you have to write an algorithm, with all permutation and combinations whose sum of digits is given number.