Help in a problem from Coding Ninjas hiring test

help
,
1

Ninja is playing with his alphabet toys. He has all the 26 lowercase alphabets. His granny wanted him to learn some maths as well.

So, she added a cost with each of the alphabets, gave him a cost array and gave him an integer. Let us denote the integer by symbol target. She asks Ninja to find the greatest word (with or without meaning) under the following constraints:

  1. The cost array is 0 indexed and cost of using alphabet at index i is given by cost[i] (Note: ‘a’ is denoted by index 0, ‘b’ is denoted by index 1 and so on)
  2. The total expenditure of characters used must be equal to target.

You have to help Ninja to print the greatest word. If you are unable to form any word, under the given constraints, then print “0”.

Note: If two words are given to you, then the greater of the two will be the one which comes later in the dictionary. For example, “hi” is greater than “hello”.

1 <= target <= 10000
1 <= cost[i] <= 10000

link : https://classroom.codingninjas.com/app/classroom/me/2617/content/54608/offering/618180/problem/7041

Kindly help me with the approach

1 Like
2

Approach :Greedy

Start selecting from largest alphabets with available target (targe-arr[i]…where i is selected alphabet)
if for this selected “i” target is not zero at last backtrack and choose next alphabet i.e (i-1).

Summary:
Use concept similar to backtracking ,try out all possibilities greedily.
Time Complexity: 26*target.

1 Like
3 
/*      Chill raho be kuch nhi rakha sadness me. 
               Author: Maskman_lucifer                   */
               
#include <bits/stdc++.h>   
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long 
#define pll pair<ll,ll>
#define pb push_back
#define M 1000000007
#define lc '\n'
using namespace std;
int main()
{
    IO
    ll a[26];
    for(ll i=0;i<26;i++)
    {
        cin>>a[i];
    }
    ll n;
    cin>>n;
    ll dp[n+1];
    dp[0]=1;
    for(ll i=1;i<=n;i++)
    {
        for(ll j=26;j>=1;j--)
        {
            if(a[j-1]<=i and dp[i-a[j-1]]>0)
            {
                dp[i]=j;
                break;
            }
            else
            {
                dp[i]=0;
            }
        }
    }
    string s1="";
    char c[26];
    char p='a';
    for(ll i=0;i<26;i++)
    {
        c[i]=p;
        p++;
    }
    if(dp[n]==0)
    {
        cout<<0<<lc;
    }
    else
    {
        while(n!=0)
        {
            s1+=c[dp[n]-1];
            n-=a[dp[n]-1];
        }
        cout<<s1<<lc;
    }
    return 0;
}

This is my solution using DP.
Just try to place Largest possible character at the end of every sum.

2 Likes
4

Thanks it helped.
Can you help me with this code, I think in worst case the complexity should be exponential but it passes all tests.

string ans;
int solve(vector<int> &a, int pos, int target){
    if(target == 0)
        return 1;
    else if(target < 0){
        return -1;
    }
    
    int cur = -1;
    for(int i = 0; i < 26; ++i){
        cur = solve(a, pos +1, target - a[i]);
        if(cur == 1){
            ans += 'z' - i;
			return 1;
        }
    }
    return -1;
}

calling this function from main and a[0] represents ‘z’ and so on.

5

Gothcha, their test cases are weak, it would definitely tle and on adding memoization it will get better.