dexhop
BAN USERn choose k for 220 (k) heads out of 400 (n) coin tosses gives the number of possible outcomes where you get exactly 220 heads. This would be:
outcomes = factorial(400) / (factorial(220) * factorial(400 - 220))
The probability of this happening would be outcomes divided by the total number of possible states flipping a coin 400 times could result in:
outcomes / 2 ^ 400
Since the questions says "at least 220 heads," you need to add the probabilities of getting 220, 221, 222, ..., 400 heads together.
The nHeadsOrMore function below does this by using Java's arbitrary precision class, BigDecimal.
I get ~2.55%
BigDecimal factorial(int n)
{
if (n == 0 || n == 1)
{
return BigDecimal.ONE;
}
BigDecimal rv = BigDecimal.ONE;
for (int i = 2; i <= n; ++i)
{
rv = rv.multiply(new BigDecimal(i));
}
return rv;
}
BigDecimal nChooseK(int n, int k)
{
if (n < k)
{
return BigDecimal.ZERO;
}
else if (n == 1)
{
return BigDecimal.ONE;
}
return factorial(n).divide(factorial(k).multiply(factorial(n - k)));
}
BigDecimal nHeadsOrMore(int numHeads, int numTosses)
{
BigDecimal result = BigDecimal.ZERO;
BigDecimal numPossibleOutcomes = (new BigDecimal(2)).pow(numTosses);
for (int i = numHeads; i <= numTosses; ++i)
{
result = result.add(nChooseK(numTosses, i));
}
return result.divide(numPossibleOutcomes);
}
Right, it is O(N^2). The get_index function takes O(N) and is called N times. We could store the source list's random addresses in a hash table (address as key and index as value), and then look them up in the get_index function. That would take O(N) for creating the hash table, and O(1) for the lookup.
- dexhop October 24, 2014#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
struct Node *random;
} Node_t;
void copy_list(Node_t *src, Node_t *dst);
void print_list(Node_t *list);
int get_index(Node_t *list, Node_t *n);
int main(int argc, char **argv)
{
Node_t src;
src.next = (Node_t *)malloc(sizeof(Node_t));
src.next->next = (Node_t *)malloc(sizeof(Node_t));
src.next->next->next = NULL;
src.random = src.next->next;
src.next->random = src.next;
src.next->next->random = &src;
src.data = 1;
src.next->data = 2;
src.next->next->data = 3;
printf("SRC:\n");
print_list(&src);
Node_t dst;
copy_list(&src, &dst);
printf("DST:\n");
print_list(&dst);
dst.random->data = 7;
printf("SRC:\n");
print_list(&src);
printf("DST:\n");
print_list(&dst);
/* should cleanup all dynamically allocated memory here */
return 0;
}
void copy_list(Node_t *src, Node_t *dst)
{
if (dst == NULL) return;
/* copy data and next pointers before copying random pointer */
Node_t *tmpdst = dst;
Node_t *curnode = src;
while (curnode != NULL)
{
tmpdst->data = curnode->data;
if (curnode->next != NULL)
tmpdst->next = (Node_t *)malloc(sizeof(Node_t));
else
tmpdst->next = NULL;
curnode = curnode->next;
tmpdst = tmpdst->next;
}
/* setup random pointers */
tmpdst = dst;
curnode = src;
while (curnode != NULL)
{
if (curnode->random != NULL)
{
int idx = get_index(src, curnode->random);
Node_t *tmpdst2 = dst;
while (idx > 0)
{
tmpdst2 = tmpdst2->next;
--idx;
}
tmpdst->random = tmpdst2;
}
else
{
tmpdst->random = NULL;
}
tmpdst = tmpdst->next;
curnode = curnode->next;
}
}
void print_list(Node_t *list)
{
/* print data from next */
Node_t *curnode = list;
while (curnode != NULL)
{
printf("%d -> ", curnode->data);
curnode = curnode->next;
}
printf("NULL\n");
/* print data from random */
curnode = list;
while (curnode != NULL)
{
printf("%d : ", curnode->data);
if (curnode->random == NULL)
printf("NULL");
else
printf("%d", curnode->random->data);
printf("\n");
curnode = curnode->next;
}
}
int get_index(Node_t *list, Node_t *n)
{
int idx = 0;
Node_t *curnode = list;
while (curnode != NULL)
{
if (curnode == n)
return idx;
++idx;
curnode = curnode->next;
}
return -1;
}
Outputs:
SRC:
1 -> 2 -> 3 -> NULL
1 : 3
2 : 2
3 : 1
DST:
1 -> 2 -> 3 -> NULL
1 : 3
2 : 2
3 : 1
SRC:
1 -> 2 -> 3 -> NULL
1 : 3
2 : 2
3 : 1
DST:
1 -> 2 -> 7 -> NULL
1 : 7
2 : 2
7 : 1
// Assuming N rows and M columns
void change_pixels(char *grid, int N, int M, int x, int y, char new_pixel)
{
// stride per row in bits
int stride = M * 3;
int bit_offset = y * stride + x * 3;
int byte_offset = bit_offset / 8;
int shift = bit_offset % 8;
// read two bytes in case pixels are on byte boundary
short int *tmp = (short *)(grid + byte_offset);
short int tmp_pixels = *tmp;
// store surrounding pixel bits (shift, one's complement and AND), and insert (OR) our new pixel bits
tmp_pixels = tmp_pixels & ~(7 << shift);
tmp_pixels = tmp_pixels | ((short int)new_pixel << shift);
*tmp = tmp_pixels;
}
mistake:
should be:
- dexhop February 02, 2015