Balanced bit array

You are given a bit array (i.e each element is 0 or 1) A[1..n].
A bit array is called balanced if the number of times 01 appears is same as the number of times 10 appears. By 01 appearing we mean that A[i] = 0 and A[i+1] = 1 for some i.
i.e.
S1 = { i : A[i] = 0 and A[i+1] = 1}
S2 = { j : A[j] = 1 and A[j+1] = 0}
The array is balanced if number of elements in S1 is same as number of elements in S2.
Eg: A = [1,0,1] is balanced.
A = [0,0,0,0,0,0] is balanced too.
Give an algortihm to determine if a bit array A[1...n] is balanced.

Solution : 

a simple way to explain this would be to consider this as a switch.
0 - OFF state
1 - ON state
01  - switch going from OFF to ON.
10 - switch going from ON to OFF.
If the 1st and last element are the same then that means that the switch has been toggled even no. of times. Hence no. of 01's and 10's are equal.

Convert a number from one base to another

Convert a number from given in base B1 to a number in base B2

public class KthMaxSum {
 public static void main(String[] args) {
  int decimal = 10;
  int binary = 2;
  for (int i = 0; i < 20; i++) {
   convertBase(i, decimal, binary);
  }
 }

 private static void convertBase(int number, int fromBase, int toBase) {
  int result = 0, i = 0;
  while (number > 0) {
   result = result + (number % toBase)
     * (int) (Math.pow(fromBase, i++));
   number /= toBase;
  }
  System.out.println(result);
 }
}

Find repeated and missing number

Given an array of size n. It contains numbers in the range 1 to n.Each number is present at least once except for 2 numbers. Find the missing numbers ?
Method I :
Assume array a ={1,2,3,3,5};
element n=3 is repeated and m=4 is missed.
Sum of the elements  actual = 1+2+3+3+5
Sum of the elements  expected = 1+2+3+4+5
Diff expected-actual = 4-3=m-n   ==> m-n=1     ----------------- Eq1
expected product = 1*2*3*3*5;
actual product     = 1*2*3*4*5;
expected/actual = 3/4=n/m ===> 3m=4n;   --------------------Eq2
We have two equations.We can find m and n now.


Method II : We can solve it using bitwise opertions.

1.Calculate XOR of all the array elements.
2.XOR the result with all numbers from 1 to n =>x1
3.After 2nd step, all elements would nullify each other except 2 missing elements(let x and y) and x1 will contain XOR of x and y
4.All the bits that are set in x1 will be set in either x or y. Get the rightmost set bit from x1.
5.divide the elements of the array in two sets – one set of elements with same bit set and other set with same bit not set. By doing so, you will get x in one set and y in another set. 
6.XOR all the elements of 1st set with the numbers between 1 to n which have same bit set and XOR the 2nd set with the numbers between 1 to n which have same bit not set. Now result of both set will have the desired result
Method III : We can solve it using hashmap also.

Count number of set bits in a number

Brian Kernighan’s Algorithm:
Subtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit(including the righmost set bit). So if we subtract a number by 1 and do bitwise & with itself (n & (n-1)), we unset the righmost set bit. If we do n & (n-1) in a loop and count the no of times loop executes we get the set bit count.
Beauty of the this solution is number of times it loops is equal to the number of set bits in a given integer.

1 Initialize count: = 0
2 If integer n is not zero
(a) Do bitwise & with (n-1) and assign the value back to n
n: = n&(n-1)
(b) Increment count by 1
(c) go to step 2
3 Else return count

/* Function to get no of set bits in binary
   representation of passed binary no. */
int countSetBits(int n)
{
    unsigned int count = 0;
    while (n)
    {
      n &= (n-1) ;
      count++;
    }
    return count;
}

Method 2 :

int countSetBits(unsigned int n)
{
  unsigned int count = 0;
  while(n)
  {
    count += n & 1;
    n >>= 1;
  }
  return count;
}

Find missing number in an array

An array A[1...n] contains all the integers from 0 to n except for one  number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer.


http://groups.google.com/group/algogeeks/browse_thread/thread/73f0092cb54b1904

Program to Find One Elements Which Occurs Only Once Except it All Occurs Thrice

You are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.

Fastest way to find that single integer
eg:
Input: [2,1,4,5,1,4,2,2,4,1]
Answer: 5

http://shashank7s.blogspot.com/2011/03/wap-for-find-one-elements-which-occurs.html

swap the two nibbles in a byte

http://www.cembedded.com/2009/04/how-to-swap-two-nibbles-in-byte.html

http://vijayinterviewquestions.blogspot.com/2007/07/how-to-swap-two-nibbles-in-byte.html


Reverse bits of a given number : http://geeksforgeeks.org/?p=726

sum two numbers using bitwise operators

Java code : 

public class AddTwoNumbers {

private static int myAdd(int a, int b)
{
int carry = a & b;
int result = a ^ b;
while(carry != 0)
{
int shiftedcarry = carry << 1;
carry = result & shiftedcarry;
result ^= shiftedcarry;
}
return result;
}

public static void main(String[] args){
System.out.println(myAdd(4, 5));
System.out.println(myAdd(4, -5));
System.out.println(myAdd(-4, -5));
System.out.println(myAdd(-4, 5));
System.out.println(myAdd(0, 5));
}
}

output :
9
-1
-9
1
5

Explanation : When you add two one-bit quantities, you get a two-bit
result :  0 + 0 = 00, 0 + 1 = 01, 1 + 0 = 01, and 1 + 1 = 10.
Note that the leftmost bit of sum of the the single-bit quantities A
and B, obeys the logic A & B, and the rightmost bit obeys A ^ B, where
& is the logical AND operation and ^ is the logical eXclusive OR
operation. When adding a multibit binary number, the leftmost bit
carries into the next bit position. So the code you presented just
does the multibit addition using the above two rules on all bits in
parallel. The first two statements determine the results using the
"leftmost bit" and "rightmost bit" rules above. If there are any
carries, then they must be added to the next position to the left.
Thus, shift the carries left one bit and repeat the addition process
using the leftmost and rightmost bit rules again. Do this until there
are no remaining carries.


Difference of two numbers : 
How to do subtraction of two integers widout using subtractn?? 
    The negative integer can be represented in 2's complement format.So sub_result=a+(~b+1) will perform the subtraction of a and b.
            -b=(~b+1). 


Refer : http://www.geeksforgeeks.org/archives/18324