Update
It seems that it is simply not possible to do this. Someone also sent me a copy of a different exam where almost the same question was asked, but with the difference that instead of being able to remove from any position you could remove only from beginning or start. Most likely the question was copied with an error. Now I only have to prove this and request the question exam be reevaluated.
A few weeks ago, in an examen in a course on Data Structures and Algorithms I was given the following problem. I couldn't resolve it in the given time then and although I will probably pass the course, I have been trying since yesterday to come up with a solution so I may improve my skills.
The problem
Given an integer n we repeatedly eliminate a digit from any position, until we are left with a number of only one digit. The function PC(n) is defined as the maximum numbers of squares of integers obtainable by the described procedure.
For example PC(32492) = 3. Two possible sequences are:
- 32492 -> 3249 -> 324 -> 24 -> 4
- 32492 -> 3249 -> 349 -> 49 -> 9
Now design an algorithm that can calculate PC(n) in polynomial time in d, where d is the number of digits in n. Assume you have a way to test if a number is square of an integer in O(1) time.
What I tried so far
The first approach obviously is to test every possible sequence and return the maximum. If I'm not mistaken this is O(d!).
Improving on the brute force method, I added a HashMap where I stored all values that have already been calculated. This way we can use a O(1) lookup to avoid having to calculate the same value twice. This is obviously an improvement in real time used, but I'm having a hard time getting a lower bound on the time complexity. So, as far as I can see, this is not polynomial.
I also tried some greedy algorithm approaches, but as expected I found for every algorithm (that I could think of) a case where it didn't choose optimally.
Any help would be greatly appreciated. I tried looking online for similar problems, but have had no luck so far.