Is there any way to use one while loop in this code instead of 2?

Question

i'm kinda new to this and have just learnt loops. so i wanted to enter 187654321, 998765432 in but i think this thing i wrote is so inefficient that it just timed out :/ it works for smaller numbers tho! would appreciate any help/tips hehe :')

import java.util.*;

class PowerOf3 {
  
  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    
    System.out.print("Enter start and end: ");
    int start = sc.nextInt();
    int end = sc.nextInt();
    
    int ans = countNumbers(start, end);
    
    
    System.out.println("Answer = "+ans);
  }
  
  // Count the number of integers from start to
  // end (both inclusive) that are power of 3
  public static int countNumbers(int start, int end) {
    int count = 0;
    if (start == 1) {
      count = -1;
    } else {
    count =0;
    }
    while (end>=start) {
      double n = end;
      while (n>1) {
        n = (double) n/3;
      }
      if (n==1) {
        count++;
      }
      end--;
    }
    return count;  // stub, to be replaced by your code
  }
}

Answer 1

Replace the following code

double n = end;
      while (n>1) {
        n = (double) n/3;
      }
      if (n==1) {
        count++;
      }

With this one and try to run,

int n = end;
      while (n%3 == 0) {
        n /= 3;
      }
      if (n==1) {
        count++;
      }

mod and integer operations can save time.

Answer 2

I've tried with a HashSet that stores all the powers_of_3 (from 3^0 to 3^19, considering integer). That code produces almost the similar timing as @abhimanyue.

Then I modify @abhimanyue's code keeping in mind with what the program actually doing, here is my code.

class PowerOf3_final 
{
    //public static Set<Integer> powerOf3 = new HashSet<Integer>();
    
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);
        
        //System.out.print("Enter start and end: ");
        
        int start = 19683;      //int start = sc.nextInt(); 
        int end = 1162261467;   //int end = sc.nextInt();
        
        long st = System.currentTimeMillis();
        
        /*
        int pow3=1;
        for(int i =0; i<20; i++) {
            powerOf3.add(pow3);
            pow3 *= 3;
        }
        */
        
        System.out.println("Answer = "+countNumbers(start, end));
        
        long en = System.currentTimeMillis();
        
        System.out.println("Execution time = "+(en-st)+" milli seconds.");
    }
      
    // Count the number of integers from start to
    // end (both inclusive) that are power of 3
    public static int countNumbers(int start, int end) 
    {
        int count = 0;
        
        if (start == 1) {
          count = -1;
        } 
        
        while (end>=start) 
        {
            /*
            double n = end;         
            while (n>1) {
                n = (double) n/3;
            }
            if (n==1) {
                count++;
            }
            */
            
            int n = end;
            while (n%3 == 0) {
              n /= 3;
            }
            if (n==1) {
              count++;
              end /=3;  // no need to check other values,
            }
            
            /*
            if(powerOf3.contains(end)) {
                count++;
            }
            */
            
            else end--;
        }
        return count;  // stub, to be replaced by your code
    }
}

This code runs superfast for all the inputs (within integer range). Still there are scope to improve the timing of this code.

Answer 3

The key to doing this quickly is not to check all numbers, which you are doing with the while (end>=start) { /* ... */ end--; }.

There are about 2 billion numbers between 1 and Integer.MAX_VALUE (the extreme case of the inputs), only 20 of which are powers of 3.

And, if you can find a power of 3, you can find the next largest one straight away by multiplying it by 3. Of course, the easiest place to start is 1.

Since there are only 20 possible values in your range, just iterate over all 20 (or until you exceed end), count the number which happen to fall within the input range. This will be so fast that it's not worth worrying about trying to start at a larger power of 3 that's within the range.

Just start at 3⁰, keep doing to 3¹⁹.

int limit = 1 + (int) Math.floor(Math.log(Integer.MAX_VALUE) / Math.log(3));  // 20.

return (int)
    IntStream.iterate(1, i -> i * 3)    // A stream containing only powers of 3
        .limit(limit)                   // Stop before you overflow
        .takeWhile(i -> i <= end)
        .filter(i -> i >= start)        // Take the ones in the range.
        .count();

Or, with a basic loop:

int count = 0;
int p = 1;
while (p <= end) {
  if (p >= start) ++count;

  if (p > Integer.MAX_VALUE / 3) break;

  p *= 3;
}
return count;

This approach takes <1μs to solve the worst-case problem (1 to Integer.MAX_VALUE) (once warmed up); and seems to only be around 10x slower without warmup.

Answer 4

The problem with your code is not efficiency. your code suffer from infinite loop

You use (int variable) type which has maximum value of 2147483647

when you exceed this number inside (increment ++) the loop, the loop will not end rather the number will circle like the following 1 2 3 4 then -4 - 3 -2 -1 or in you example: 2147483646, 2147483647, then 2147483647-, 2147483646-, etc..