1 day ago

Sarthak • 10

Hyderabad

Problem1: Maximize Three-Digit Integer

Problem Statement:

Write a function solution that, given a three-digit integer N and an integer K, returns the maximum possible three-digit value that can be obtained by performing at most K increases by 1 of any digit in N.

Examples:

1. Given N = 512 and K = 10, the function should return 972. The result can be obtained by increasing the first digit of N four times and the second digit six times.
2. Given N = 191 and K = 4, the function should return 591. The result can be obtained by increasing the first digit of N four times.
3. Given N = 285 and K = 20, the function should return 999. The result can be obtained by increasing the first digit of N seven times, the second digit once, and the third digit four times.

Assumptions:

• N is an integer within the range [100..999].
  (Further constraints on K apply based on standard test cases).

Problem2: Maximize Blog Signs from Catalogue

Problem Statement:

There is a company that sells large letters made out of wood and metal (similar to the ones spelling "HOLLYWOOD"). The company is going out of business, and the owners want to sell off their remaining stock. They have listed all the remaining letters in a catalogue in a string S (in no particular order), and have advertised their "Everything must go" offer online.

Attracted by the reduced prices, Alice has decided to order some letters from the company. She wants to build as many signs with the name of her new blog as possible and place them around the city. She hasn't decided on the name of her blog yet, and is considering K different possibilities. Right now she is wondering about the maximum number of signs she can build if she chooses one of the names from her list.

Knowing the list of possible names of Alice's blog L and the company catalogue state S, find the maximum number of copies of a name from L that Alice can build.

Example Test Cases (from compiler output):

1. Catalogue S = 'BILLOBILLOLLOBBI', Names L =
   ['BILL', 'BOB']
2. Catalogue S = 'CAT', Names L =
   ['ILOVEMYDOG', 'CATS']
3. Catalogue S = 'ABCDXYZ', Names L =
   ['ABCD', 'XYZ']

4 hours ago

Rohit • 30

Hyderabad

Problem 1 Solution: Maximize Three-Digit Integer Solution

Topics Involved / Prerequisites

• Greedy Algorithms
• Digit Extraction / String Manipulation

Overview

To maximize the final value of a number, the most significant digits must be prioritized. A +1 increase on the hundreds digit adds 100 to the total value, whereas a +1 on the ones digit only adds 1. Therefore, we should greedily apply our K available increments to the hundreds digit until it reaches 9, then move to the tens digit, and finally the ones digit.

Approach

1. Extract Digits: Convert the integer N into a list or array of its three individual digits.
2. Greedy Increment: Iterate through the digits from left to right (index 0 to 2).
3. For each digit, calculate how much we can add to it. We can add either the amount needed to reach 9 (which is 9 - current_digit) or the remaining K, whichever is smaller.
4. Update the digit, subtract the added amount from K, and move to the next digit.
5. Reconstruct: Combine the three digits back into a single integer.

C++ Implementation

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int maximizeThreeDigit(int N, int K) {
    string s = to_string(N);

    for (int i = 0; i < 3; ++i) {
        int current_digit = s[i] - '0';
        
        
        int add_amount = min(9 - current_digit, K);
        s[i] = (char)(current_digit + add_amount + '0');
        K -= add_amount;
        
     
        if (K == 0) {
            break;
        }
    }
            
    // Reconstruct the integer from the string
    return stoi(s);
}

Time and Space Complexity

• Time: O(1) — The number of digits is always exactly 3, so the loop runs in constant time.

Space: O(1) — We only store a few variables for the three digits.

4 hours ago

Rohit • 30

Hyderabad

Problem 2 Solution

Maximize Blog Signs from Catalogue

Topics Involved / Prerequisites

• Hash Maps / Frequency Counting
• String Processing

Overview To determine how many times a specific word can be formed from a pool of letters, we need to compare the frequency of each character required by the word to the frequency of that character available in the catalogue. The maximum number of signs for a single name is bottlenecked by the limiting character (the character that runs out first).

Approach

1. Catalogue Frequency: Count the occurrences of each letter in the catalogue string S using a hash map or frequency array.
2. Evaluate Each Name: For every potential blog name in the list L, count the occurrences of each letter required to spell it.
3. Find the Bottleneck: For a single name, iterate through its required characters. The number of times we can form this name is the available count in S divided by the required count in the name (integer division). The minimum of these quotients across all unique characters in the name is the maximum number of signs we can build for that specific name.
4. Maximize Overall: Track the maximum signs buildable across all the different names in L and return that maximum.

C++ Implementation-:

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int maximizeBlogSigns(const string& S, const vector<string>& L) {
    // Count available letters in the catalogue
    unordered_map<char, int> catalogue_counts;
    for (char c : S) {
        catalogue_counts[c]++;
    }
    
    int max_total_signs = 0;
    
    for (const string& name : L) {
     
        unordered_map<char, int> name_counts;
        for (char c : name) {
            name_counts[c]++;
        }
        
        int possible_copies = 1e9;
        
        // Check how many times we can spell this specific name
        for (const auto& pair : name_counts) {
            char char_needed = pair.first;
            int count_needed = pair.second;
            
            // Integer division to find out how many times we can satisfy this character
            int copies_of_char = catalogue_counts[char_needed] / count_needed;
            possible_copies = min(possible_copies, copies_of_char);
        }
            
        // Update the global maximum if this name yields more signs
        max_total_signs = max(max_total_signs, possible_copies);
    }
        
    return max_total_signs;
}

Time and Space Complexity

• Time: O(|S| + |L| * M) — Where |S| is the length of the catalogue and M is the average length of the names in L. We iterate through the catalogue once, and then through each character of each name.
• Space: O(1) — Because the alphabet is limited to 26 uppercase English letters, the frequency maps will never exceed a constant size of 26.