Help needed for a BFS problem

help
1

You are given an old touch smartphone numbers having dial pad and calculator app.
The goal is to type a number on dial-pad.
Calculator have 1-9 and +, -, * , /, = as operations. But as the phone is old, some of the numbers and some operations can’t be touched.
But you can always make a number using other numbers and operations. There could be multiple ways of making a number. You have to find minimum operation for making a number.

For ex: let’s say 1,4,6,7,8,9 works and +,-,* works.
2,3,5 and / doesn’t work.

If you have to type 18-> 2 operations. (Each touch is considered an operation).

If you have to type 5 → ‘1+4=’ that requires 4 operations. There could be other ways to make ‘5’.

The goal is to find minimum operations.

Link to the question: You are given an old touch sma | CareerCup
Please help me in understanding the approach. Thank you :slight_smile:

1 Like
2

I was thinking this problem could be done using BFS but I am not getting how to implement it. Can you please help. :slight_smile:

1 Like
3

So here is the solution:-

1)BFS an Queue.

2)Use a Queue, and store all the allowed numbers in it :slight_smile:

3)On each number of the queue, pop it out , and do the operations given to you, say the number is x, then do x+(?) , then x-(?),also do x(?–>Appending) and all allowed operations I mean…(?) means combination of all the numbers which are allowed(less than x), so you get ‘y’ after doing this operation, check if ‘y’ is the number you wanted…if not, then push it into the queue, with the number of operations required to reach ‘y’, keep doing this till you reach a ‘y’ which is equal to the answer :slight_smile: . Set an upper limit like 10000 iterations for the queue, if you are not able to find the answer in those iterations, answer is No , not possible to reach that number! :slight_smile:

To improve the efficiency, you can stop searching in some nodes(backtracking :stuck_out_tongue: ) :slight_smile:
I’ll write its code soon!!

1 Like
4

Maybe we can append numbers too… Like we can do 76 - 67 = 9 (to get 9 from 6, 7 and - ). This approach does not handle those cases, I guess?

1 Like
5

I did not read the question carefully, I thought appending the numbers is not allowed, wait I am editing it.
Update:-Now, it handles appending as well :slight_smile:

1 Like
6

Would it be right to pop a number from the queue? Maybe we get a number at a very later stage which needs to be paired with a number obtained much earlier and has been popped?

7

Mmmmm…I guess you did not understand what I was doing, popping out has no effect on the final number you want :slight_smile:

8

Suppose you need to do 35 - 7 = 28
We reached 7, did all possible operations with it and moved on by popping it. Now 3 came after it and we created 35. Now we need 7 but it would be popped.
Am I missing something?

1 Like
9

What are the allowed numbers and operations ??

0,1,3,5,7,9 and +…-…/

1 Like
10

Step:-1
Queue:–>(0,1,3,5,7,9)

Step-2:- We reach ‘3’ suppose, we can do 3+(),3-(),3/(), 3()…

Step 3:- When we do 3() and all other stuff we get 30,35,31,37,39,33…and all other numbers from (+.- and /)

Step 4:- 3 has been popped out after the above step…

Step 5:- Lets look at 35…we can do 35+(), etc… and 35()…–> appending…

Step 6:—> If we do 35-(all possible guys),now what are the possible guys? They are all combinations (you generate them )of (0,1,3,5,7) of length <=2 like :- 0,1,3,5,7,71,30,73,etc…

Step 7:- Say you pick up (7) from all the possible guys and you do (35-7)=28

:slight_smile:

1 Like
11

Okay, now I got it. You generate all possible numbers of required digits in each operation. :slightly_smiling_face::slightly_smiling_face:

1 Like
12

And time complexity is kind of infinite :slight_smile:
But it is allowed, because the official solution to this question uses backtracking, which can take infinite time as well :stuck_out_tongue:

We can stop our searching if we are getting numbers whose length is 3 to 4 times larger than what we want…

1 Like
13

Yes, the problem itself is pretty ambiguous. :stuck_out_tongue:

1 Like
14

Yup, its posted by a random person with no official links…he says it is from Samsung but there is no guarantee…

I like such weird questions as interviewer does not use test-case like codechef to check our solution :stuck_out_tongue:

1 Like
15

Can you help me with this?