The a-b-c Calculator Filename: calc.java Standard Input, Standard Output You bou

Question

The a-b-c Calculator Filename: calc.java Standard Input, Standard Output You bought a calculator at a garage sale for only 25 cents, thinking you got a steal Unfortunately, the calculator has very limited functionality and a rather strange screen. The initial display always starts with 0 on it and there are three buttons you can press which perform the followi ng operations on the current number on the screen (1) Add a (2) Multiply by b (3) Integer Division by c where a, b, and c are given for each different calculator The screen displays exactly 6 digits, and when you attempt a calculation with a result one million or greater, you realize that the display shows the last six digits of the actual correct response and uses this value instead for the next calculation. (For example, if the display showed 345678 and b = 3, if we press the button to multiply by 3, the resulting value will be 037034, the last six digits of the actual result. If we then pressed the integer divide button by c = 4, the new result would be 9258. Note that this is different than 1037034/4.) Given the constants a, b, and c, described above, and a target integer, t, determine the minimum number of button presses needed to obtain t on the calculator display The first line will contain a single positive integer, n, (n s 100), specifying the number of input cases. Each input case will be on a single line having four space-separated positive integers, a b, c and t, representing the additive constant, multiplicative constant, division constant and target value for the test case (1 s a, b, Cs 1000, 1 sts 999999) Output For each test case, on a line by itself, output the minimum number of button presses necessary to obtain the target for the case. If it's impossible to obtain the target, print out a -1 on a line by itself instead Samples Output 1 3 2 197 10 30 1 5 1 7 2 123456 1 17

Explanation / Answer

Find the JAVA code below.

import java.util.*;

/*
* The approach could be to use BFS here.
* BFS finds the target node with minimum number of edges given that edges have same weight.
* The minimum number of steps could be considered as the edges.
*/
class Ans {
   public Integer value;
   public Integer steps;
  
   Ans(Integer v, Integer s) {
       value = v;
       steps = s;
   }
  
   @Override
   public String toString() {
       return "Ans [value=" + value + ", steps=" + steps + "]";
   }
}
public class calc {
   public static Integer a;
   public static Integer b;
   public static Integer c;
   public static Integer t1;
  
    static Integer BFS()
    {
       // As the targe value could not be greater than 10^6 we can have
       // visited array of 10^6.
        boolean visited[] = new boolean[1000000];

        // Queue used in BFS.
        LinkedList<Ans> queue = new LinkedList<Ans>();

        visited[0]=true;
        queue.add(new Ans(0,0));

        while (queue.size() != 0)
        {
            Ans s1 = queue.poll();

            // check if we have found the target value.
            // if so return the number of steps. As in BFS we will reach in
            // minimum number of steps.
            if(s1.value.equals(calc.t1))
               return s1.steps;
          
            // Add element in queue based on the condition.
          
            // Assuming next element to be current plus a
            Integer add = (s1.value+calc.a)%1000000;
          
//            Assuming next element to be current multiplied by b
            Integer mult = (s1.value*calc.b)%1000000;
          
//            Assuming next element to be current divided by c
            Integer divide = (s1.value/calc.c)%1000000;
          
            if(!visited[add]) {
               visited[add] = true;
               queue.add(new Ans(add,s1.steps+1));
            }
            if(!visited[mult]) {
               visited[mult] = true;
               queue.add(new Ans(mult,s1.steps+1));
            }
            if(!visited[divide]) {
               visited[divide] = true;
               queue.add(new Ans(divide,s1.steps+1));
            }
          
            // Add the element only if they are not visited.
            // Re adding elements will cause redundancy in computation.
        }
      
        // Once queue is empty return -1 as the target element is unreachable.
        return -1;
    }
  
   public static void main(String[] args) {
       Scanner in= new Scanner(System.in);
      
       // Take input from user.
       int t = in.nextInt();
       for(int i =0; i<t; i++) {
           a = in.nextInt();
           b = in.nextInt();
           c = in.nextInt();
           t1 = in.nextInt();
          
           System.out.println(BFS());
       }
      
      
       in.close();
   }
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.