Interview Question Number Complement

By Fatih KABAKCI

The problem is to find out complement of a number.

Problem #476 - Number Complement

Description: Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:
1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
2. You could assume no leading zero bit in the integer’s binary representation.


Example 1:
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2:
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

Difficulty: Easy

Solution in Java

package com.fatihkabakci.Easy.NumberComplement;

/**
 * @author fkabakci
 * Problem Description: Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.
 * 
 * Note:
 * 		1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
 * 		2. You could assume no leading zero bit in the integer’s binary representation.
 * 
 * Example 1:
 * Input: 5
 * Output: 2
 * 
 * Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
 * 
 * Example 2:
 * Input: 1
 * Output: 0
 * 
 * Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.
 * 
 * Solution:
 * 1. Find out the bits.
 * 2. Figure out powers of 2 times complement value and adds result.
 */

public class Solution {
	private int getBitLength(int number) {
		int i = 0;
		for (i = 0; i < 31 && number >= Math.pow(2, i); i++);
		return i;
	}
	
	private byte[] toBits(int number) {
		return toBits(number, getBitLength(number));
	}

	private byte[] toBits(int number, int bitLength) {
		int capacity = getBitLength(number);
		if (bitLength < capacity) {
			bitLength = capacity;
			System.err.println("Attempt to override capacity !");
		}

		byte[] bits = new byte[bitLength];
		for (int i = bitLength; number > 0; i--) {
			bits[i - 1] = (byte) (number % 2);
			number = number / 2;
		}
		return bits;
	}

	public int findComplement(int num) {
		byte[] bits = toBits(num);
		int l = bits.length;
		int complement = 0;
		for (int i = 0; i < l; i++) {
			byte bit = (byte) ((bits[i] == 0) ? 1 : 0);
			complement += bit * Math.pow(2, l - 1 - i);
		}
		return complement;
	}

	public static void main(String[] args) {
		int complement = new Solution().findComplement(2);
		System.out.println(complement);
	}
}