what is the best algorithm to solve this programming challenge ? Given a positive integer number consisting only of digits 6 and 9

Question

Given a positive integer num consisting only of digits 6 and 9.

Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).

Example 1:

Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666. 
The maximum number is 9969.

Example 2:

Input: num = 9996
Output: 9999
Explanation: Changing the last digit 6 to 9 results in the maximum number.

Example 3:

Input: num = 9999
Output: 9999
Explanation: It is better not to apply any change.

Answer 1

Traverse from left to right and change the first occurrence of 6 to 9. If there is not any 6 while traversal then does not change any digit. Following code may help:-

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class testing {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc=new Scanner(System.in);
        System.out.print("Enter a number : ");
        int a=sc.nextInt();
        String numberString = Integer.toString(a);

        for (int i = 0; i < numberString.length(); i++){
            char c = numberString.charAt(i);
            if(c=='6') { // check if the digit is 6 or not, if 6 is present then change it to 9
                numberString = numberString.substring(0, i) + '9' + numberString.substring(i + 1);
                break; // break the loop if 6 is changed to 9
            }
        }
        System.out.println("Largest Number is : "+numberString);
    }


}

Answer 2

public class Maximum69 {
public static void main(String[] args) {
    int num=6669;
        int added = 0;
        int cur = 1;
        int curNum = num;
        while(curNum > 0) {
            if(curNum % 10 == 6)
                added = cur;
            cur *= 10;
            curNum = curNum / 10;
        }
       System.out.println(num + added * 3);

}

}

I found out how to slove, This takes less time to run:

Answer 3

I have found a formule, it could have been a single line solution but for clarity I have divided in two lines

• First , get the highest number based on input number of digits , for example if input is 6, topNumber will be 9, for 69 top will be 99 , for 696 top is 999, so topNumber can be 9 or 99 or 999 or 9999 or 99999,etc up to java limit, the formula to get number of digits in an integer is :
  floor(log10(input)) + 1
• Then you can notice that the top number minus the input, it gives you a number that starts with 3, for example 9-6 = 3 , 99 - 69 = 30 , 999 - 696 = 303, except when the input is equal to the top number, in that case the result is 0,
• knowing that fact, we can conclude that for switching the first 6 in the number can be achieved by summing up 3 * (((the position of the 6) -1) * 10) , eg. 3 or 30 or 300 or 3000 or 30000, etc.
• resulting in the last part of the function : input + (10^(NumberOfDigits(top - input)) -1) * 3

private static int largest69(int number) {  
        int topNumber = (int) (Math.pow(10,(int)(Math.log10(number)) + 1) -1);
        return  number + (int) Math.pow(10,(( (int)(Math.log10(topNumber - number)) + 1 ) -1) ) * 3;        
    }

Answer 4

If you're not as good as nitinsridar at intuitively implementing math into your algorithm, and if you don't want to mess around with strings like backdoor did, then you can utilize data structures to help you come to a solution without much thought

public static void main(String[] args) {
    System.out.println(maxNumber(9669));
}

public static int maxNumber(int number) {
    Stack<Integer> numbers = new Stack<Integer>();

    int numberLength = 0;
    while(number > 0) {
        numbers.push(number % 10);
        number /= 10;
        numberLength++;
    }

    boolean changedFirstOccurrence = false;
    int maxNumber = 0;
    for(int i = numberLength; i > 0; i--) {
        int numberToAdd = numbers.pop();
        if (numberToAdd == 6 && !changedFirstOccurrence) {
            numberToAdd = 9;
            changedFirstOccurrence = true;
        }
        maxNumber += numberToAdd * (int) Math.pow(10, i);
    }
    return maxNumber / 10;
}

Is this the best solution? Nope, I would go with nitinsridar's answer (I also believe that his/her answer should get the green checkmark).

Backdoor's answer is definitely how I would've solved this problem before I took my data structures and algorithms class. I'm not saying it's a bad answer. In fact, his algorithm is more concise than mine. It's just my opinion that you don't want to get in the habit of relying on string manipulation to solve these sort of "numerical" problems, because one day it's not going to work; in this case, it did. I'm just providing another way of doing it