650. 2 Keys Keyboard

There is only one character 'A' on the screen of a notepad. You can perform one of two operations on this notepad for each step:

• Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).
• Paste: You can paste the characters which are copied last time.

Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen.

Example 1:

Input: n = 3
Output: 3
Explanation: Initially, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Example 2:

Input: n = 1
Output: 0

Constraints:

• 1 <= n <= 1000

Approach 01:

#include <numeric>
#include <vector>

class Solution {
public:
    int minSteps(int totalA) {
        if (totalA <= 1)
            return 0;

        // steps[i]: the minimum steps to get i 'A's
        std::vector<int> minStepsForA(totalA + 1);

        // Copy 'A', then paste 'A' i - 1 times.
        std::iota(minStepsForA.begin(), minStepsForA.end(), 0);

        for (int currentA = 2; currentA <= totalA; ++currentA) {
            for (int divisor = currentA / 2; divisor > 2; --divisor) {
                if (currentA % divisor == 0) {
                    minStepsForA[currentA] = minStepsForA[divisor] + currentA / divisor; // Paste minStepsForA[divisor] currentA / divisor times.
                    break;
                }
            }
        }

        return minStepsForA[totalA];
    }
};

class Solution:
    def kthSmallest(self, array, k):
        # Find the maximum value in the array
        maxValue = 0
        for num in array:
            if num > maxValue:
                maxValue = num

        # Create a boolean array to track the presence of each value
        presence = [0] * maxValue

        # Mark the presence of each value in the boolean array
        for num in array:
            presence[num - 1] = 1

        # Find the k-th smallest element by counting marked values
        count = 0
        kthSmallestElement = 0
        for i in range(maxValue):
            if presence[i] == 1:
                count += 1
                kthSmallestElement = i + 1
                if count == k:
                    break

        return kthSmallestElement

Time Complexity

• Initialization with iota:

  The function std::iota initializes the minStepsForA vector with sequential values, which takes \( O(n) \) time, where \( n \) is totalA.

• Outer Loop:

  The outer loop runs for every value of currentA from 2 to totalA, contributing \( O(n) \) to the time complexity.

• Inner Loop:

  The inner loop, which checks for divisors of currentA, iterates approximately \( O(\sqrt{n}) \) times for each currentA, where \( n \) is totalA.

• Overall Time Complexity:

  The overall time complexity is \( O(n \sqrt{n}) \), where \( n \) is totalA.

Space Complexity

• Space for minStepsForA Vector:

  The minStepsForA vector requires \( O(n) \) space to store the minimum steps for each value of totalA.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \), where \( n \) is totalA.