650. 2 Keys Keyboard

650. 2 Keys Keyboard

https://leetcode.com/problems/2-keys-keyboard/description/

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        

Approach-1. Count

Logic

  • We donot need to copy all characters on notepad all times.

Number of characters needed on notepad: 5
Operation Characters on notepad  Steps
 Copy         A                   1
 paste        AA                  2
 paste        AAA                 3    //if we have copied(AA), then we never had reached 5
 paste        AAAA                4
 paste        AAAAA               5

Number of characters needed on notepad: 6
Operation Characters on notepad  Steps
 Copy         A                   1
 paste        AA                  2
 copy         AA                  3
 paste        AAAA                4
 paste        AAAAAA              5
 paste        AAAAA               5        

  • At each step, we need to check whether we can reach(desired no of characters using copy of present chars on notepad) or we donot need copy

if ((number of still chars needed) % (chars on notepad presently) == 0)
  We can copy and paste characters
else
  We cannot copy just paste the characters copied earlier        

Complexity

  • Time: O(n)
  • Space: O(1)

Code

CPP

class Solution {
    public int minSteps(int n) {
        int charCountOnNotepad = 1;  // Number of characters present on notepad
        int charsInCopiedBuffer = 0;        // Number of characters present in buffer after Cntl^C
        int steps = 0;
        while (charCountOnNotepad < n){  // Iterate until we have n characters on notepad
            int neededCharsOnNotepad = n - charCountOnNotepad;
            if (neededCharsOnNotepad % charCountOnNotepad == 0) {
                /*
           Condition-1: Needed characters are multiple of character on notepad,
                               We can copy all characters and paste all
                               steps = 2 (copy, paste)
                */
                charsInCopiedBuffer = charCountOnNotepad;
                charCountOnNotepad += charCountOnNotepad;
                steps += 2;
            }else if (charsInCopiedBuffer!=0 && (neededCharsOnNotepad % charsInCopiedBuffer == 0)){
         /*
           Condition-2: Needed characters are not multiple of character on notepad,
                               We cannot copy all characters on notepad, only option is
                 Just paste chars copied earlier
                               Steps=1 (paste)
                */
                charCountOnNotepad += charsInCopiedBuffer;
                steps++;
            } else {
                return -1;
            }
        }
        return steps;
    }
}        

要查看或添加评论,请登录

Amit K.的更多文章

  • Pyunit or Unitest

    Pyunit or Unitest

    Used to test a unit of source code Features: 1. PyUnit is very simple yet very flexible 2.

  • Calling OpenAI APIs from code

    Calling OpenAI APIs from code

    Steps a. Get openAI API Key openaAI API Key b.

    3 条评论
  • FlatList with Example in React Native

    FlatList with Example in React Native

    What is FlatList? displays a scrolling list of changing, but similarly structured, data. Unlike the more generic…

  • Create Postgres Database, Tables, Schema using Diesel(ORM) Rust

    Create Postgres Database, Tables, Schema using Diesel(ORM) Rust

    What is Diesel Diesel is a ORM(object-relational mapping). ORM is programming technique that connects object-oriented…

  • Location Sharing App System Design (Bump)

    Location Sharing App System Design (Bump)

    What is Bump Bump is location sharing Mobile App. Install bump on 2 phones(add as friends).

  • Load Balancers & Caches

    Load Balancers & Caches

    What is Load Balancer? Load Balancer evenly distributes incoming traffic/load among webservers/workers that are defined…

  • REST API / Representation State Transfer

    REST API / Representation State Transfer

    Restful Web Server/Application? Web application that implements HTTP CRUD methods in Restful way. Eg: Twitter, facebook…

  • Inter Thread Communication in Rust using Channels

    Inter Thread Communication in Rust using Channels

    What is Channel? Sender and Receiver are connected via Channel. They can send/recv data via channel.

  • Slices in Rust

    Slices in Rust

    What is Slice Slice is somepart of larger data, it always borrow data(Hence RO) from the sliced type. It gives you a…

  • Traits in Rust

    Traits in Rust

    What is Triat in Rust Interface/class in Rust(declared with keyword trait) having Virtual Functions(not pure Virtual)…

社区洞察

其他会员也浏览了