karaamaati
BAN USER@AAT @maillist, isn't O(logn) better than O(n).
- karaamaati October 04, 2013Construct an undirectional graph G(V, E), where
V = set of Bar Codes.
E(V1, V2) = true, if V1 and V2 don't differ in more than 2 bits.
Number of bags = Number of connected component in Graph G.
Number of bits two number differ can be calculated by counting number of 1's in XOR of the numbers.
@Miguel Oliveria, isn't the ans for the test case given by you is 6:
v = { 1, 3, 1, 1, 1, 1 }
r = { 1, 2, 1, 1, 0, 0 }
The best is 6 by taking 5th, 6th, 4th and then 2nd bombs respectively.
Here is an implementation of the first approach.
#include<stdio.h>
#include<stdlib.h>
typedef enum {false, true} bool;
typedef struct BVect_s {
char *val;
int len;
int numBit;
} BVect;
int initialize(BVect *v){
v->val = (char *)malloc(sizeof(char));
v->len = 1;
v->numBit = 0;
return 0;
}
bool get(BVect *v, int pos){
if(v->numBit <= pos)
return false;
int s = sizeof(char);
return v->val[pos/s]&(1<<(pos%s))?true:false;
}
int set(BVect *v, int pos, bool a){
if(pos >= v->numBit)
return 1;
int s = sizeof(char);
if(a)
v->val[pos/s] = v->val[pos/s]|(1<<(pos%s));
else
v->val[pos/s] = v->val[pos/s]&~(1<<(pos%s));
return 0;
}
int doubleLen(BVect *v){
v->len *= 2;
return v->val = realloc(v->val, sizeof(char)*v->len);
}
int append(BVect *v, bool a){
if(v->val == NULL)
initialize(v);
if(v->numBit == v->len*8)
doubleLen(v);
v->numBit++;
return set(v, v->numBit-1, a);
}
/*driver function to test*/
int main(){
char op;
int val, pos;
BVect *t;
while(1){
scanf("%c", &op);
switch(op){
case 'a':
scanf("%d", &val);
append(t, val);
break;
case 's':
scanf("%d", &pos);
scanf("%d", &val);
set(t, pos, val);
break;
case 'g':
scanf("%d", &pos);
printf("%d\n", get(t, pos));
}
}
return 0;
}
Can be done as following:
1. use two pointers with x and 2x speed to find the mid node and whether the length of array is even or odd.
2. traverse the list for second time to find the node to delete, while tracking if it comes before mid or not.
3. if length is odd and element to delete is mid or before mid, set newMid to next of mid. If length is even and deleted element is mid or after mid set newMid to prev of mid.
4. delete the node. if newMid is not NULL, set the end of modified list to newMid.
#include<stdlib.h>
typedef struct list_s {
int val;
struct list_s *next;
} list;
list *delete(list *head, int val)
{
if(head == NULL)
return head;
list *t1, *t2, *prev, *mid, *newMid = NULL;
enum {even, odd} length;
/*find the mid and length(odd/even) using two runners*/
t1 = head;
t2 = t1->next;
while(t1 != t2 && t1 != t2->next){
t1 = t1->next;
t2 = t2->next->next;
}
if(t1 == t2)
length = odd;
else
length =even;
mid = t1;
/*search for node to delete and track if node is previous to the mid*/
enum {false, true} isPrevToMid = true;
t1 = head;
prev = NULL;
while(t1->next != mid || isPrevToMid = true){
if(t1 == mid){
isPrevToMid = false;
/*if length is odd, newMid is prev element to mid*/
if(length == odd)
newMid = prev;
}
if(t1->val == val)
break;
prev = t1;
t1 = t1->next;
}
/*if node not found, return the same list*/
if(t1->val != val)
return head;
/*set newMid to next of mid if length is even and node to be deleted is prevToMid*/
if((isPrevToMid == true || t1 == mid) && length == even)
newMid = mid->next;
if(prev == NULL){ /*if the node is head, modify the head*/
if(head->next == head)
head = NULL;
else
head = head->next;
}
else /*else remove node from the list*/
prev->next = t1->next;
/* if newMid is not NULL, find the end node in the modified list and set it to newMid,*/
if(newMid != NULL){
t2 = t1;
while(t2->next != mid || isPrevToMid == true){
if(t2 == mid)
isPrevToMid = false;
t2 = t2->next;
}
t2->next = newMid;
}
free(t1);
return head;
}
My approach is as follow:
-Transform K such that K[i] = number of integers 0.. K[i] missing before K[i] in K[]
-Generate a random number x = uniform(0... N-K.length-1)
-Find y = number of numbers equal to or less than x in K[], using binary search.
-return x+y
Time = O(K.length) Space = O(1)
Working C code below
- karaamaati November 02, 2013