DattaP
BAN USERIn this special case of (x+1)^N
if we have binomial coefficient == 1, the number will have a 1 in it.
This program used this property to calculate number of 1's in the final number without calculating the number.
unsigned int binomial_coefficient(int n, int k) {
if (k < 0 or k > n)
return 0;
if (k == 0 or k == n)
return 1;
k = std::min(k, n - k);
int c = 1;
for (int i=0; i < k; i++)
c = c * (n - i) / (i + 1);
return c;
}
unsigned int ones_in_power_of_eleven(int N) {
std::vector<unsigned int> binomial_coeffs(N+1);
for (int k=0; k <= N/2; ++k) {
unsigned int c = binomial_coefficient(N,k);
binomial_coeffs[k] = c; // binomial coefficients are symmetric
binomial_coeffs[N-k] = c;
}
for (int i=0; i < N; i++) {
unsigned int coeff = binomial_coeffs[i];
unsigned int cahead = coeff / 10;
unsigned int remainder = coeff % 10;
binomial_coeffs[i] = remainder;
binomial_coeffs[i+1] += cahead;
}
int ones = 0;
for (int i=0; i <= N; i++) {
if (binomial_coeffs[i] == 1)
ones++;
}
return ones;
}
This C++ version has just one loop, however uses std::remove which might be doing some looping on the non_repeating char vector.
char find_first_nonrepeating(const std::string& str) {
std::map<char, int> index_map;
std::vector<char> vec;
for (auto ch : str) {
auto it = index_map.find(ch);
if (it == index_map.end()) {
vec.push_back(ch);
index_map.insert(std::pair<char,int>(ch, static_cast<int>(vec.size())));
} else {
int it2 = it->second;
if (it2 != -1) {
vec.erase(std::remove(vec.begin(), vec.end(), ch), vec.end());
index_map[ch] = -1;
}
}
}
if (vec.size())
return vec[0];
else
return '\0';
}
I wrote this program to solve the Skyline problem of UVA 41.
This solves the problem in nlogn complexity. and requires no more than O(n) space.
import heapq as hq
buildings = [(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)]
#1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0
points = list()
for idx, building in enumerate(buildings):
points.append((building[0], building[1], idx+1))
points.append((building[2], building[1], -idx-1))
points.sort(key=lambda tup: tup[0])
points_q = list()
current_h = -1
current_x = -1
deleted_nodes=dict()
for point in points:
current_x = point[0]
id = 0
if point[2] > 0:
hq.heappush(points_q, (-point[1],point[2]))
id = point[2]
else:
deleted_nodes[-point[2]] = True
tp = hq.heappop(points_q)
while tp[1] in deleted_nodes and points_q:
tp = hq.heappop(points_q)
if tp and tp[1] not in deleted_nodes:
hq.heappush(points_q, tp)
ll = hq.nsmallest(1, points_q)
if ll:
local_h = -ll[0][0]
else:
local_h = 0
if local_h != current_h:
current_h = local_h
print('x=', current_x, 'y=', current_h)
I agree with you, this method is less intuitive, I was trying to make it faster by reducing complexity. But it may not be possible.
- DattaP April 22, 2015