# 157. Read N Characters Given Read4     ## Approach 1: $O(2(R + W))$

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 /** * The read4 API is defined in the parent class Reader4. * int read4(char *buf4); */ class Solution { public: /** * @param buf Destination buffer * @param n Number of characters to read * @return The number of actual characters read */ int read(char* buf, int n) { char* buf4 = new char; int i4 = 0; // buf4's index int n4 = 0; // buf4's size int i = 0; // buf's index while (i < n) { if (i4 == n4) { // all characters in buf4 are consumed i4 = 0; // reset buf4's index n4 = read4(buf4); // read 4 (or less) chars from file to buf4 if (n4 == 0) // reach the EOF return i; } buf[i++] = buf4[i4++]; } return i; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 /** * The read4 API is defined in the parent class Reader4. * int read4(char[] buf4); */ public class Solution extends Reader4 { /** * @param buf Destination buffer * @param n Number of characters to read * @return The number of actual characters read */ public int read(char[] buf, int n) { char[] buf4 = new char; int i4 = 0; // buf4's index int n4 = 0; // buf4's size int i = 0; // buf's index while (i < n) { if (i4 == n4) { // all characters in buf4 are consumed i4 = 0; // reset buf4's index n4 = read4(buf4); // read 4 (or less) chars from file to buf4 if (n4 == 0) // reach the EOF return i; } buf[i++] = buf4[i4++]; } return i; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 """ The read4 API is already defined for you. def read4(buf4: List[chr]) -> int: # Below is an example of how the read4 API can be called. file = File("abcdefghijk") # File is "abcdefghijk", initially file pointer (fp) points to 'a' buf4 = [' '] * 4 # Create buffer with enough space to store characters read4(buf4) # read4 returns 4. Now buf = ['a','b','c','d'], fp points to 'e' read4(buf4) # read4 returns 4. Now buf = ['e','f','g','h'], fp points to 'i' read4(buf4) # read4 returns 3. Now buf = ['i','j','k',...], fp points to end of file """ class Solution: def read(self, buf: List[str], n: int) -> int: buf4 = [' '] * 4 i4 = 0 # buf4's index n4 = 0 # buf4's size i = 0 # buf's index while i < n: if i4 == n4: # all characters in buf4 are consumed i4 = 0 # reset buf4's index n4 = read4(buf4) # read 4 (or less) chars from file to buf4 if n4 == 0: # reach the EOF return i buf[i] = buf4[i4] i += 1 i4 += 1 return i 

## Approach 2: $O(R + W)$

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 /** * The read4 API is defined in the parent class Reader4. * int read4(char *buf4); */ class Solution { public: /** * @param buf Destination buffer * @param n Number of characters to read * @return The number of actual characters read */ int read(char* buf, int n) { char* buf4 = new char; int i4 = 0; // buf4's index int n4 = 0; // buf4's size int i = 0; // buf's index // while not reaching the tail (< 4 chars) while (i + 4 < n) { const int k = read4(buf + i); // directly write to buf if (k == 0) // reach the EOF return i; i += k; } while (i < n) { if (i4 == n4) { // all characters in buf4 are consumed i4 = 0; // reset buf4's index n4 = read4(buf4); // read 4 (or less) chars from file to buf4 if (n4 == 0) // reach the EOF return i; } buf[i++] = buf4[i4++]; } return i; } };