FastPrep

Description

Solutions

Submission

Minimum Chunks Required (Akuna Shang Hai 🌆)

🔥 FULLTIME

A financial services company is uploading documents to a compliance system for analysis. They use a chunking mechanism as below.

Each document is divided into equal sized packets.
Documents are then divided and uploaded in "chunks" of packets. A chunk is defined as a contiguous collection of 2^n packets, where n is any integer ≥ 0.
After the document is divided into chunks, randomly selected chunks are uploaded until the entire document is completely uploaded.

There is one document that is partially uploaded, described in uploadedChunks. Determine the minimum number of chunks that are yet to be uploaded.

Function Description

Complete the function minimumChunksRequired in the editor.

minimumChunksRequired has the following parameter(s):

long totalPackets: the number of packets in the document.
long uploadedChunks[n][2]: each uploadedChunks[i] describes the start and end packet numbers of the uploaded chunks.

Returns

int: an integer that denotes the minimum number of chunks that need to be uploaded.

Example 1:

Input:  totalPackets = 10, uploadedChunks = [[1, 2], [9, 10]]
Output: 2 
Explanation:
The document has 10 packets and 2 chunks of 2^1 = 2 packets are already uploaded [1, 2] and [9, 10].

The remaining 10-4 = 6 packets are uploaded in chunks. The length of chunk1 is 2^2 = 4, packets [3,4,5,6], and the length of chunk2 is 2^0 = 1 packets [7, 8].

Example 2:

Input:  totalPackets = 18, uploadedChunks = [[9, 17]]
Output: 2 
Explanation:
The document has 18 packets and 2 chunks of packets are already uploaded: [9, 10, 11, 12, 13, 14, 15, 16] and [17].

The remaining 18-2 = 16 packets are uploaded in chunks. The length of chunk1 is 2^3 = 8 packets: [1, 2, 3, 4, 5, 6, 7, 8] and the length of chunk2 is 2^0 = 1 packets: [18].

Constraints:

1 ≤ totalPackets < 10¹⁸

0 ≤ uploaded < 10⁵

The uploaded chunks do not overlap

1 ≤ starting packet ≤ ending packet ≤ totalPackets