C solution with bits and permutations of identical objects


  • 0
    V
    void permute(int * n, int start, int pos);
    void swap_bits(int * n, int bit_pos_1, int bit_pos_2);
    int mult(int high, int low);
    
    char ** arr;	// this will be our string pointer array
    int perm;		// this will keep track of it's index
    
    char ** readBinaryWatch(int num, int * returnSize)
    {
        int i, j;
        
        // calculate needed number of strings and get memory
        arr = malloc(mult(10, 10 - num) / mult(num, 0) * sizeof(*arr));
        if (NULL == arr)
    		exit(EXIT_FAILURE);
        
        // put num number of bits in i
        j = num;
        i = perm = 0;
        while (--j >= 0)
    		i |= (1 << j);
    	
    	// generate all permutations
        permute(&i, num, num);
        
        *returnSize = perm;
        return arr;
    }
    
    void permute(int * n, int start, int pos)
    {
    	if (0 == pos)
    	{
    		int hours = (*n >> 6) & 0x0F;
    		if (hours > 11)
    			return;
    		
    		int minutes = *n & 0x3F;
    		if (minutes > 59)
    			return;
    			
    		// allocate new string
    		arr[perm] = malloc(6 * sizeof(char));
    		if (NULL == arr[perm])
    			exit(EXIT_FAILURE);
    		
    		// make the string
    		sprintf(arr[perm], "%d:%.2d", hours, minutes);
    		++perm;
    		return;
    	}
    	
    	/* end result of this loop is that every 0 has been
    	 * swapped with a 1 */
    	while (start <= 10)
    	{
    		swap_bits(n, start, pos);
    		permute(n, start, pos - 1);
    		swap_bits(n, start, pos);
    		++start;
    	}
    }
    
    void swap_bits(int * n, int bit_pos_1, int bit_pos_2)
    {
    	unsigned int b1, b2, tmp;
    	
    	// use 1 based positions for simplicity
    	*n <<= 1;
    	
    	// get bits a and b
    	b1 = (*n >> bit_pos_1) & 1;
    	b2 = (*n >> bit_pos_2) & 1;
    	
    	// xor a and b to get result c
    	tmp = b1 ^ b2;
    	
    	// put result c in original bit positions
    	tmp = (tmp << bit_pos_1) | (tmp << bit_pos_2);
    	
    	// xor bits a and b with c to get b and a
    	*n ^= (int)tmp;
    	// shift back for actual number
    	*n >>= 1;
    }
    
    int mult(int high, int low)
    {
    	/* helps with shorthand calculation
    	 * of the number of permutations */
    	int ret;
    	
    	for (ret = 1; high > low; --high)
    		ret *= high;
    		
    	return ret;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.