0

How can I find the maximum and the minimum number that can be formed using digits of a given number (for example 485735) without using any array at all ?

I was looking at the algorithm of bubble sort (that using array) and I tried to figure out how to write an algorithm without the array but my problem was to counting the indexes of every digit

The only thing that cross my mind was an algorithm to count the number of digits in the input (friend helped me with that) , but so far I'm tried to figure this thing out for a 4 days that's a question with a grade from my homework

the rule is that the smallest number can't start in a zero for example:

Input: 3134059 
The largest number is: 9543310
The smallest number is: 1033459
10
  • 1
    ideone.com/n8M8BX Commented Apr 3, 2019 at 22:48
  • because we didn't learn about arrays in the Course yet so we are not allowed using that Commented Apr 3, 2019 at 23:03
  • 1
    @shmosel That won't work if there are 2 or more zeroes in the value. --- Also, I believe that using Stream::sorted(), to internally build a list and sort it, is violating the spirit of the "no array" restriction, so I'd have marked it failed, if I was the teacher grading that answer. Commented Apr 3, 2019 at 23:03
  • @Andreas yes , unfortunately i think you're right Commented Apr 3, 2019 at 23:08
  • 1
    @Andreas So are Strings altogether illegal? Commented Apr 3, 2019 at 23:08

2 Answers 2

2

TL;DR: See demo of below logic at IDEONE.

Pretend the number is an array of digits, e.g. named d[], and pretend that index 0 is the rightmost digit.

A bubblesort will move higher values to higher indexes, so if we keep that logic, sorting d would result in the desired largestNumber, e.g. 1357924 becomes 9754321.

Assume you have a method pow10(n) which calculates 10n, you can then get digit at any index:

d[i] = number / pow10(i) % 10

Example:

         6 4 2 0  index
         ↓ ↓ ↓ ↓
number = 1357924

d[4] = 1357924 / pow10(4) % 10
     = 1357924 / 10000 % 10
     = 135 % 10
     =   5

In a bubblesort, you swap adjacent elements if lower-indexed element is larger, so first we need the two values. Let's say we're doing it for i = 3:

         6 4 2 0  index
         ↓ ↓ ↓ ↓
number = 1357924
i = 3

a = d[i] = d[3] = 7
b = d[i+1] = d[4] = 5

Since a > b we need to swap the values. We can do that as follows:

 1357924
-   7000   Clear digit at i=3
-  50000   Clear digit at i=4
=1300924   Value with digits cleared
+  70000   Set digit at i=4
+   5000   Set digit at i=3
=1375924   Value with digits at index 3 and 4 swapped

The formula for that is:

number = number - a * pow10(i) - b * pow10(i+1)
                + a * pow10(i+1) + b * pow10(i)

Which can be refactored to:

number += ((a - b) * 10 - (a - b)) * pow10(i)

Now that you know how to get the "array element value", aka d[i], and how to "swap array elements" using the above formula, you write that into a normal bubblesort algorithm, so you can:

largestNumber = sortDigits(number)

You've now calculated the largest value. To calculate the smallest value, you need to simply reverse the digits, but before you do that, you need to ensure that d[0] != 0:

n = largestNumber, i = 0
while (n % 10 == 0) { // locate least non-zero digit
    n /= 10
    i++
}
if (i != 0) {
    // clear least digit and add at index 0
    n = n / 10 * pow10(i + 1) + n % 10
}

Example:

n = 97500
After loop: n = 975, i = 2
n / 10 = 97
            * pow10(i + 1) = 97000
                                   + n % 10 = 97005

Now you can calculate the other value you need:

smallestNumber = reverse(n)

See e.g. Java reverse an int value without using array for how to do that.

Sign up to request clarification or add additional context in comments.

Comments

0
public static void main(String[] args) {

    StringBuilder s = new StringBuilder("4857035");
    char aux;

    for (int i = 0; i < s.length() - 1; i++) {
        for (int j = i + 1; j < s.length(); j++) {
            if (s.charAt(i) > (s.charAt(j))) {
                aux = s.charAt(i);
                s.setCharAt(i, s.charAt(j));
                s.setCharAt(j, aux);
            }
        }
    }
    //output 0345578

    while (s.charAt(0) == '0') {
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != '0') {
                aux = s.charAt(0);
                s.setCharAt(0, s.charAt(i));
                s.setCharAt(i, aux);
                break;
            }
        }
    }
    //output 3045578
}

This is for the smallest number, for the greatest number change the sign on if statement ( if (s.charAt(i) < (s.charAt(j))) and delete the while statement.

1 Comment

Since StringBuilder internally uses a char[], I'd say that this violates the spirit of the "no array" restriction, so I'd have marked it failed, if I was the teacher grading that answer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.