CareerCup

If you remove all the 9s from a sequence of numbers in base 10, then you end up with a sequence in base 9.

So all we have to do is convert n in base 10, to base 9 and return that.

int nthNumber(int n) {
    return Integer.valueOf(Integer.toString(n, 9));
}

Cost O(nlogn). The operation of computing if a number contains a 9 is logarithmic as we check each digit we perform this operation n times.
Solution in Python:

def contains9(n):
    while (n > 10):
        if (n % 10) == 9: return True
        n /= 10
    if n == 9: return True
    return False
    
def filter9(n):
    return filter(lambda x: not contains9(x),
                    xrange(1, n+1))

Caching will definitely help. Here is how to do it in ZoomBA:

removed_9 = seq ( 0 ) ->{
    next = $.p[-1] + 1
    while ( '9' @ str(next) ){ next += 1 }
    next //return 
}
def newNumber(inx){
   if ( inx <= 0 ) return ''
   while ( inx  >= size ( removed_9.history ) ){
       removed_9.next 
   } 
   removed_9.history[inx]
}
println( newNumber(1) )
println( newNumber(8) )
println( newNumber(9) )
println( removed_9.history )

The result:

➜  zoomba99 git:(master) ✗ zmb tmp.zm
1
8
10
[ 0,1,2,3,4,5,6,7,8,10 ]
➜  zoomba99 git:(master) ✗

1) Just iterate through numbers and ignore number with digit 9 in them like the solutions above which takes nLogN time
2) We can make the above logic fast by not considering any number to the right of 9 for eg if we are at 19876 then o point going to 19877 as 9 is at position 3 so instead jump directly to 20000 or in case of 1888 jump to 2000, this will be faster but still nlogn
3) We can do this in linear time O(N) in best case scenario by:
Lets say countOccurenceOf9(n) returns number of times 9 appears until n then n th number = n + countOccurenceOf9(n) but there must be numbers contains 9 between n and n + countOccurenceOf9(n) so then we find find how many times 9 appeared between n and n + countOccurenceOf9(n) and skip by that amount and repeat

public class Solution {
  public int getNthNumber(int number, int digit) {
    if(digit < 0 || digit > 9) {
      return -1;
    }
    DigitOccurence digitOccurence = new DigitOccurence();
    int n = number;
    int numOfDigits = digitOccurence.getOccurence(n, digit);
    int numToSkip = numOfDigits;
    while(numToSkip != 0) {
      int newN = n + numToSkip; // but there might be digits between n and n+numOfDigits so we need to skip them too
      int t = digitOccurence.getOccurence(newN, digit);
      numToSkip = t - numOfDigits;
      numOfDigits = t;
      n = newN;
    }
    return this.getNumberAfterRemovinDigit(n, digit);
  }

  private int getNumberAfterRemovinDigit(int n, int digit) {
    if(result == -1) {
      return n;
    }
    int numberWithDigitsWipedOutAfterPosition = n / Math.pow(10, result);
    numberWithDigitsWipedOutAfterPosition = n * Math.pow(10, result); // Change 19899 into 19000
    return numberWithDigitsWipedOutAfterPosition + Math.pow(10, result); // 19000 + 1000 = 20000 as we need to remove 9 from number
  }

  private int getMostSygnificantDigitPosition(int n, int digit) {
    int position = 0;
    int result = -1;
    while(n > 0) {
      if(n % 10 == digit) {
        result = position;
      }
      position++;
      n = n / 10;
    }
    return result;
  }

  /********************************** Code below is to find number of occurences of digit d until number n****/
  public class DigitOccurence {
    public int getOccurence(int number, int digit) {
      number = Math.abs(number);
      if(digit < 0 || digit > 9) {
        return 0;
      }

      Map<Integer, Integer> cache = new HashMap<>();
      return this.getOccurence(number, digit, cache);
    }

    private int getOccurence(int number, int digit, Map<Integer, Integer> cache) {
      // Every digit appears once from 0 - 9
      if(number < 10) {
        return 1;
      }
      // Every digit appears 19 (conting 22 as one occurence in this case) times from 0 - 99 except 0 which appears 10 times
      else if(number < 100) {
        return digit == 0 ? 10 : 19;
      }
      else if(cache.hasKey(number)) {
        return cache.get(number);
      }

      int numDigits = this.getNumDigits(number);
      int msd = this.getMostSygnificantDigit(number);
      int numButMsd = number - msd * Math.pow(10, numDigits - 1); // get 98 out of 898
      /**
      Here is the magic:
      => C(898, digit) = C(0-799, digit) + C(800-898, digit) //  msd is 8, numButMsd is 98
      => C(799, digit) = C(99, digit) * 8 + (digit < 8) ? 100 : 0
      => C(800-898, digit) = C(98, digit) + (digit == 8) ? 99 : 0;
      => C(898, digit) = (C(799, digit) = C(99, digit) * 8 + (digit <= 6) ? 100 : 0)
        + (C(98, digit) + (digit == 8) ? 99 : 0);
      */
      int occurence = (msd * this.getOccurence(Math.pow(10, numDigits - 1) - 1, digit, cache) + (digit < msd) ? Math.pow(10, msd - 1) : 0)
        + (this.getOccurence(numButMsd, digit, cache) + digit == msd ? numButMsd + 1 : 0);
      cache.put(number, occurence);
      return occurence;
    }

    private int getNumDigits(int number) {
      int count = 0;
      while(number > 0) {
        count++;
        number = number / 10;
      }
      return count;
    }

    private int getMostSygnificantDigit(int number) {
      if(number == 0) {
        return 0;
      }
      int numDigits = this.getNumDigits(number);
      return number / Math.pow(10, number - 1);
    }
  }
}

public static void removenine()
		{
			for(int count=1; count<=100; count++)
			{
				String numberAsString = Integer.toString(count);
					if (numberAsString.contains("9"));
				
					else 
					{ 
						System.out.println(numberAsString);
					}
						
			}
		}