Shutterfly Interview Question: For any positive integer n, d... | Glassdoor

Interview Question

Software Engineer Interview

For any positive integer n, define d(n) to be n plus the

  sum of the digits of n. For example, d(75) = 75 + 7 + 5 = 87. The number n is called a generator of d(n). Some numbers have more than one generator: for example, 101 has two generators, 91 and 100. A number with no generators is a self-number. There are thirteen self-numbers less than 100: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, and 97. Write a function that returns the number of positive self-numbers less than a number, threshold.
Answer

Interview Answer

2 Answers

0

public class Program
{
    public static void Main()
    {
        int number =100;
        Console.WriteLine(findTotalNumbers(number));
    }

    static int findTotalNumbers(int number)
    {
        if(number == 2)
            return 1;
        if(hasGenerator(number,number) == true)
            return findTotalNumbers(number-1);
        else
            return findTotalNumbers(number-1)+1;
    }

    static bool hasGenerator(int number,int original)
    {
        if(number == (original-18))
            return false;
        if((number + findSumofDigits(number)) == original)
            return true;
        return hasGenerator(number-1,original);
    }

    static int findSumofDigits(int number){
        if(number == 0 )
            return 0;
        else
            return ((number%10) +findSumofDigits(number/10));
    }
}

I will use a combination of dynamic programming programming and recursion on Nov 11, 2015
0

function findNumber(n){
 var num = [false];
 var res = [];
 for(var i = 1; i <= n; i++){
     if(num[i] === undefined){
      num[i] = true;
  }
  var sum = i+findDigitsSum(i);
  if(sum < n){num[sum] = false;}
 }
 for(var i = 1; i < n; i++){
     if(num[i]){
      res.push(i);
  }
 }
 return res;
}
function findDigitsSum(n){
    if(n < 10){
      return n ;
  }
  return n%10 + findDigitsSum(parseInt(n/10));

}
console.log(findNumber(100))

rain on Feb 26, 2018

Add Answers or Comments

To comment on this, Sign In or Sign Up.