Algorithm
Problem link- https://www.spoj.com/problems/BIGSEQ/
BIGSEQ - Sequence
You are given the sequence of all K-digit binary numbers: 0, 1,..., 2K-1. You need to fully partition the sequence into M chunks. Each chunk must be a consecutive subsequence of the original sequence. Let Si (1 ≤ i ≤ M) be the total number of 1's in all numbers in the ith chunk when written in binary, and let S be the maximum of all Si, i.e. the maximum number of 1's in any chunk. Your goal is to minimize S.
Input
In the first line of input, two numbers, K and M (1 ≤ K ≤ 100, 1 ≤ M ≤ 100, M ≤ 2^K), are given, separated by a single space character.
Output
In one line of the output, write the minimum S that can be obtained by some split. Write it without leading zeros. The result is not guaranteed to fit in a 64-bit integer.
Example
Input: 3 4 Output: 4
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
pw = [1] * 105
for i in range(1, 105):
pw[i] = pw[i - 1] * 2
def countBits(N, K):
count = 0
for i in range(K):
count += N // pw[i + 1] * pw[i]
count += max(0, N % pw[i + 1] - pw[i] + 1)
return count
def findUpperBound(bitCount, low, high):
middle, best = 0, 0
while low <= high:
middle = (low + high + 1) >> 1
if countBits(middle, K) <= bitCount:
best = middle
low = middle + 1
else:
high = middle - 1
return best
K, M = map(int, raw_input().split())
highestResult = countBits(1 << K, 102) / M + 50
lowestResult = max(1, highestResult - 111)
low, high, best, middle = lowestResult, highestResult, highestResult, 0
while low <= high:
middle = (low + high + 1) >> 1
skippedNumbers, skippedBits = 0, 0
for i in range(M):
if skippedNumbers >= pw[K] - 1:
break
skippedNumbers = findUpperBound(skippedBits + middle, skippedNumbers + 1, pw[K] - 1)
skippedBits = countBits(skippedNumbers, K)
if skippedNumbers >= pw[K]- 1:
best = middle
high = middle - 1
else:
low = middle + 1
print(best)Input
Output
Demonstration
SPOJ Solution-Sequence-Solution in C, C++, Java, Python