Disney + Hotstar | OA Coding Questions and Solutions | Set - 1 | 2022

Question

All past online assesments of Disney + Hotstar can be found using the tag "disney_hotstar_oa" in the search bar.

Here is the link :https://www.desiqna.in/tag/disney_hotstar_oa

Answer 1

Alice is a smart student who is very good at math. She is attending a math class. In this class, the teacher is teaching the students how to use a calculator. The teacher will tell an integer to all of the students, and the students must type that exact number into their calculators. If someone fails to type the number, he or she will be punished for failing such an easy task!

 

Unfortunately, at the beginning of the class, Alice finds that her calculator is broken! She finds that some of the number buttons are totally broken, and only the "multiply" and "equals" operator buttons are available to use. So she can only use these buttons to get the number quickly.

 

For instance, the teacher may say the number "60", while Alice's calculator can only type "1", "2" and "5". She could push the following buttons:

 

Button "15" (2 clicks)

 

Button "multiply" (1 click)

 

Button "2" (1 click)

 

Button "multiply" (1 click)

 

Button "2" (1 click)

 

Button "equals" (1 click)

 

This method requires 7 button clicks. However, if Alice uses "12*5=", only 5 clicks are needed. Of course Alice wants to get the integer as fast as possbile, so she wants to minimize the number of button clicks. Your task is to help her find a way to get the required number quickly.

 

Input

 

The first line of the input gives a number T, the number of integers the teacher says. T test cases follow.

 

Each case contains two lines. The first line contains ten numbers each of which is only 0 or 1. the ith number (starting from 0) is "1" if the number i can be clicked, or "0" if it is broken. The second line contains only one number X, the integer the teacher tells everyone.

 

Output

 

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of button clicks needed, or "Impossible" if it is not possible to produce the number.

 

SAMPLE

 

INPUT

 

3

 

0 1 1 0 0 1 0 0 0 0

 

60

 

1 1 1 1 1 1 1 1 1 1

 

128

 

0 1 0 1 0 1 0 1 0 1

 

128

 

OUTPUT

 

Case #1: 5

 

Case #2: 4

 

Case #3: Impossible

 

CONSTRAINTS

 

1 <= T <= 100

 

1 <= X <= 10^6

Comments

#include <bits/stdc++.h>
using namespace std;

bool check(int a[], int num) {
    
    bool ans = true;
    
    while(num > 0) {
        int temp = num%10;
        ans = ans & (a[temp]);
        num /= 10;
    }
    
    return ans;
}

int count_digit(int i) {
    int ans = 0;
    
    while(i>0) {
        ans++;
        i /= 10;
    }
    
    return ans;
}

int main() {
    
    int t;
    cin>>t;
    
    for(int p=1;p<=t;p++) {
        
        int a[10];
        
        for(int i=0;i<10;i++) {
            cin>>a[i];
        }
        
        int target;
        cin>>target;
        
        int dp[target+1];
        
        memset(dp, INT_MAX, sizeof(dp));
        
        // for(int i=0;i<10;i++) {
        //     if(a[i] == 1) {
        //         dp[i] = 1;
        //     }
        // }
        
        if(check(a, target)) {
            dp[target] = count_digit(target);
        }
        else {
            for(int i=0;i<=target;i++) {
                
                if(check(a, i)) {
                    dp[i] = count_digit(i);
                } else {
                    if(target%i != 0) continue;
                    int temp = INT_MAX;

                    for(int j=2;j<=sqrt(i);j++) {
                        if(i%j==0 && dp[i/j] != INT_MAX && dp[j] != INT_MAX) {
                            temp = min(temp, dp[j] + dp[i/j] + 1);
                        }
                    }

                    dp[i] = temp;
                }
            }
        }
        // for(int i=0;i<=target;i++) {
        //     cout<<i<<" "<<dp[i]<<endl;
        // }
        
        if(dp[target] == INT_MAX) {
            cout<<"Case #"<<p<<": Impossible"<<endl;
        } else {
            cout<<"Case #"<<p<<": "<<dp[target]+1<<endl;
        }
    }
    
    return 0;
}