is there some solution to reduce the time complexity of a program in java?

Vikas Aggarwal 0
Viewed 80

The question is

Given a number 'N'. The task is to find the Nth number whose each digit is a prime number(<10) i.e 2, 3, 5, 7. In other words you have to find nth number of this sequence : 2, 3, 5, 7, 22, 23 ,.. and so on.

I'm trying the below code which exceeds the time bound.

import java.io.*; 
import java.util.*; 


class Main {

    public static boolean AlldigitsPrime(int m){
        for(; m>0;){
            int dig=m%10;
            if(dig!=2 && dig!=3 && dig!=5 && dig!=7){
                return false;
            }
            m/=10;
        }
        return true;
    }
    
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0; i<t; i++){
            int n=sc.nextInt();
            int count=0;
            for(int j=2; j>=2 ; j++){
                if(AlldigitsPrime(j)){
                    count++;
                    if(count==n){
                        System.out.println(j);
                        break ;
                    }
                } 
            } 
        }
    }
}
time-complexity java
1 Answers

You can calculate the n-th number almost directly. The idea is to convert n into a new number system in which no number contains a 0 digit (apart from the leading ones which are ignored) but consists only of digits 1 to 4. That is: 1 -> 1, 4 -> 4, 5 -> 11, 6 -> 12, 9 -> 21 and so on. The last step is to replace each digit (1 to 4) by its correspondig prime number (2, 3, 5 or 7).

Although I usually refrain from giving example code for homework, but because it's a bit complicated, I'll show the solution:

public int convert(int n) {
    if (n < 1) throw new IllegalArgumentException("n must be positive but was " + n);
    int[] primes = {2,3,5,7};
    int result = 0;
    int power = 1;
    do {
        int digit = (n-1) % 4 + 1; // we don't want 0es
        result += primes[digit - 1] * power;
        power *= 10;
        n = (n-1) / 4;             // take the 'removed' 0es into consideration
    } while (n > 0);
    return result;
}

Of course, addition and subtraction of 1 in the first two lines of the loop is not necessary but I kept it there to highlight the 'removal' of 0es while calculating the digits.

Mihe0
Related