One Line Java Solution


  • 34
    D

    This is a radix problem.
    Just change decimal to 9-based.

    public int newInteger(int n) {
        return Integer.parseInt(Integer.toString(n, 9));
    }
    

    Of course, you can write it yourself.

    public int newInteger(int n) {
    	int ans = 0;
    	int base = 1;
    		
    	while (n > 0){
    		ans += n % 9 * base;
    		n /= 9;
    		base *= 10;
    	}
    	return ans;
    }
    

  • 2
    D

    May you give more detail about why it works? Thank you so much~


  • 9
    D

    I try to explain why it works.
    As the problem want to move every digit has 9, which means 1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 18 20... That is once you count to 8, we need jump to 10( which luckily 9 in 9 based )... And when change number in 9 base, it will not appear 9 any more...
    It only useful to move 9, and not suit for other digit, such as 8.. since in 8 base, will get list as this : 1 2 3 4 5 6 7 10 11.. will pass 9..


  • 0
    F

    @donggua_fu
    His answer is very clear. "change decimal to 9-based." For example, Binary is 2-based and Hexadecimal is 16-based. Wikipedia has complete explanation of how this works.


  • 0
    D

    @frostzyh Yeah, I really know how to change a digit to 9-based, I just not very clear why it works, and this method suit to what kind of problem.
    I am sorry if I don't make things clear or if I asked some very stupid question~~(^_^)


  • 3
    F

    @donggua_fu

    In case you don't know the api, here is the link
    http://docs.oracle.com/javase/8/docs/api/java/lang/Integer.html

    To help you understand, we can think that for every additional 9 numbers from 0, base-9 would be 1 number larger than base-10. So 0 + 9 is 10 in base-9 and 9 in base 10.

    Let me give you some example:
    for n = 10, 10/9 = 1 R 1. We can think this as one unit of 9 so the number in base-9 system would be 1 number larger than decimal. so the result is n + 1 = 10 + 1 = 11.
    for n = 100, 100/ 9 = 11 R 1. We can think that n has 11 units of 9s. Then 11 units in 9-base is 11 + 11/9 = 11 + 1 = 12. So the value in base-9 system is n + 12 * 1 = 100 + 12 = 121.

    These explanation is just for helping understanding, hope you can get the trick.


  • 1
    C

    @donggua_fu
    It's the first time I saw this kind of radix problem, it also feels to be like a magic. Here is my thought:

    Given a sorted array of numbers in base-10: 1, 2, 3, 4, ... Since each number that contains 9 was excluded, the only possible numbers left are 0-8, looks like 9-based right ? But are they in ascending order and increment by one ? The answer is fortunately yes !
    Because:
    1, Every possible number n expressed in 9-based are in the sequence of '1', '2', '3', '4', ... since this sequence already exhausts every possibility of number combinations using 0-8
    2, Since this sequence is in ascending order in 10-based expression, it must be in ascending order in 9-based expression. Why ? Think of how you compare two numbers intuitively in 10-based situation: 100 > 99 because 100 has more digits, 98>97 because 9==9, and 8>7. This also applies to any n-based number system including 9-based.

    Since every possible number in 9-based system presents in the sequence after you "remove-9" and they are in ascending order, they must be exactly incrementing one by one in 9-based system.

    Now, forget about "removing 9", just write down the ascending sequence in 9-based system:
    '1' ,'2',...'8', '10','11','12'... ->9 based
    The related ordering would be
    1, 2, ... 8, 9, 10, 11,...
    Given an input number n, you just convert it into 9-based, for example, convert 2->'2', 9->'10', 10->'11', 11->'12'. That converted number if you look at it in 10-based system is the output


  • 0
    D

    @captainjtx @frostzyh Yeah, Thanks so much for your patient (^^)~ I get it now.. Thanks ~~(^^)


  • 1
    H

    What if the question is to remove 8?


  • 0
    G

    @frostzyh

    You're losing me. n + 12 * 1 = 100 + 12 = 121? That doesn't add up. Can you re-explain the 100 example?


  • 0
    T

    @gidpfefffer
    1.ans = 100%91 = 0+1 = 1
    n = 100/9 = 11
    2.ans = 11%9
    10 = 1+ 210 = 21
    n = 11/9 = 1
    3.ans = 1%9
    100 = 21+100 = 121


  • 3
    C

    @huangw3
    I think it still works if thinking in the way that I mentioned. In this case, you can pretend that 9 is actually 8 and tweak the conversion between 9-radix and 10 radix. Given number n, convert it to 9-radix but replace all digits of 8 with 9 and look at it in 10-based.


  • 1
    K

    @donggua_fu If someone still doesnt understand, check out this link https://betterexplained.com/articles/numbers-and-bases/ . Surprisingly its too trivial and many of us have forgotten this .


  • 0
    C

    This approach is not correct because after converting the number to base 9 equivalent, the result generated is also a number in base 9. The problem expects the result to be a number in base 10.
    eg consider input n = 18
    In base 10, the series, after removing 9, will be:
    1,2,3,4,5,6,7,8,10,11,12,13,14,15,16,17,18,19
    output - 19 (correct)
    If number is converted to base 9, the series will be:
    1,2,3,4,5,6,7,8,10,11,12,13,14,15,16,17,18,20
    output - 20 (which is not correct)


  • 0
    K

    @coder_saket The problem does not expect the answer to be in base 10. Also, output 20 is correct for n=18. Think of it this way -
    Base 10_ 1,2,3,4,5,6,7,8,9 ,10,11,12,13,14,15,16,17,18,19,20
    Base 9_ _1,2,3,4,5,6,7,8,10,11,12,13,14,15,16,17,18,20,21,22

    Clearly, when n = 18, meaning the 18th integer not having 9 => 18th integer in base 9 => 20. Which is correct.


  • 0
    E

    @frostzyh said in One Line Java Solution:

    @donggua_fu
    His answer is very clear. "change decimal to 9-based." For example, Binary is 2-based and Hexadecimal is 16-based. Wikipedia has complete explanation of how this works.

    Which Wikipedia article specifically are you referring to? (link please)


  • 0
    C

    @khader With base 9, answer 20 is correct. But I would assume base to be 10 unless explicitly specified and hence expect 19 to be correct answer.


  • 0
    V
    This post is deleted!

  • 0
    V

    @eRCaGuy He's talking about this page which has lot of information.


  • 0
    V

    @captainjtx No. It's not that simple to assume same for remove 8 problem. What would your answer be for n= 8? in remove 9 problem it's 8 but for remove 8, it should be 9. There will be such corner cases because there is hole(missing 8) in number space if we assume as you've suggested.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.