263 - Number Chains - UVA Online Judge

Number Chains

Given a number, we can form a number chain by

1. arranging its digits in descending order
2. arranging its digits in ascending order
3. subtracting the number obtained in (2) from the number obtained (1) to form a new number
4. and repeat these steps unless the new number has already appeared in the chain

Note that 0 is a permitted digit. The number of distinct numbers in the chain is the length of the chain. You are to write a program that reads numbers and outputs the number chain and the length of that chain for each number read.

Input and Output

The input consists of a sequence of positive numbers, all less than , each on its own line, terminated by 0. The input file contains at most 5000 numbers.

The output consists of the number chains generated by the input numbers, followed by their lengths exactly in the format indicated below. After each number chain and chain length, including the last one, there should be a blank line. No chain will contain more than 1000 distinct numbers.

Sample Input

123456789
1234
444
0

Sample Output

Original number was 123456789
987654321 - 123456789 = 864197532
987654321 - 123456789 = 864197532
Chain length 2

Original number was 1234
4321 - 1234 = 3087
8730 - 378 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
Chain length 4

Original number was 444
444 - 444 = 0
0 - 0 = 0
Chain length 2

Solve of Problem

Number Chains Algorithm

1.   Get a number (M) as an integer number

2.   Check M value  If  M is a positive number greater than 0  then do next step ,  if M=0 then terminate the program , otherwise just  re input  M

3.   Set N by get a descending value of  M

4.   Set O by  an ascending value of M

5.   Set  P=N – O

6.   Set counter=1

7.   Print M as original number

8.   Do step 9 until 13 while N – O  is not same P ( I use Do … While ) , otherwise jump to step 14

9.   Print number chain ( N – O = P )

10. Set P =N – O

11. Set N by get a descending value of  P

12. Set O by get an ascending value of  P

13. Increase the counter  by 1

14. Print the counter as chain length

15. Back to step 1 for the next input until EOF

 Here is the code with java language

import java.util.Scanner;

class NumberChains {

    String getAsc(int num){

        char temp;

        char no[]=String.valueOf(num).toCharArray();

        for (int  i =0 ; i < (no.length)-1; i++) {

            for (int  j =0 ; j < (no.length)-1-i; j++) {

                if(no[j]>no[j+1]){

                    temp=no[j];

                    no[j]=no[j+1];

                    no[j+1]=temp;

                }

            }

        }

        return String.valueOf(no, 0, no.length);

    }

    String getDesc(int num){

        char temp;

        char no[]=String.valueOf(num).toCharArray();

        for (int  i =0 ; i < (no.length)-1; i++) {

            for (int  j =0 ; j < (no.length)-1-i; j++) {

                if(no[j]<no[j+1]){

                    temp=no[j];

                    no[j]=no[j+1];

                    no[j+1]=temp;

                }

            }

        }

        return String.valueOf(no, 0, no.length);

    }

    public static void main(String[] args) {

        Scanner s=new Scanner(System.in);

        NumberChains nc=new NumberChains();

        int M=-1;

        int counter;

        while(M!=0){

            M=s.nextInt();

            if(M!=0){

                int N=Integer.parseInt(nc.getDesc(M));

                int O=Integer.parseInt(nc.getAsc(M));

                counter=1;

                System.out.println("Original number was "+M);

                int P=N-O;

                do{

                    System.out.println(N+" - "+O+" = "+(N-O));

                    P=N-O;

                    N=Integer.parseInt(nc.getDesc(P));

                    O=Integer.parseInt(nc.getAsc(P));

                    counter++;

                }while(N-O!=P);

                System.out.println("Chain length "+counter);

            }

       }

    }

}