Problem Brief
Minimum Chunks Required (Akuna Shang Hai 🌆)
FULLTIMEOA
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.
1Example 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].
2Example 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
Limits and guarantees your solution can rely on.