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.

LeftShift fiddle in java

int: The int data type is a 32-bit signed two's complement integer. It has a minimum value of -2,147,483,648 and a maximum value of 2,147,483,647 (inclusive). For integral values, this data type is generally the default choice unless there is a reason (like the above) to choose something else. This data type will most likely be large enough for the numbers your program will use, but if you need a wider range of values, use long instead.

     When we shift a variable beyond it's width,then output becomes dependent on the compiler,so it is undefined behavior.

public class BitFiddle {
 public static void main(String[] args) {
  Integer i = 3;
  i = i << 31;
  System.out.println(i);// -2147483648
  System.out.println(Integer.toBinaryString(i));//10000000000000000000000000000000
  

  int j = 3;
  j = j << 32;
  System.out.println(j);// 3
  System.out.println(Integer.toBinaryString(j));//11

  int k = 3;
  k = k << 33;
  System.out.println(k);// 6
  System.out.println(Integer.toBinaryString(k));//110
 }
}

Infinite stream of Bits Divisible by 3

Given an infinite stream of bits with bits being appended at the  highest significant position. Give an algorithm to say whether the number formed by sequence of bits that had been processed till then is divisible by 3 or not ?

Solution from Algogeeks group :

Divisibility of 3 of numbers in base 2 can be seen same as divisibility of numbers by 11 in base 10.
Maintain two variable even_sum & odd_sum, both initialized to 0.When an odd location in the number is set increment odd_sum.When an even location in the number is set increment even_sum.

if(abs(even_sum-odd_sum)%3==0) number is divisible by 3.
Hence keep the track of even_sum and odd_sum as the bits are getting appended.

Number of bits set in odd position - Number of bits set in even position 'll be divisible by 3
For example, take 9. 1001. No. of bits set in odd position-number of bits set in even position is 0.Hence divisible by 3.
For 21, 10101. Difference is 3.. SO just keep count of the number of bits set in odd position and even position as the stream.

If the stream contains numbers :
For calculating the sum, no need to store all the elements sum.After adding a number each time,take modulus and store the remainder in sum.So it will not become more and will be less than 3.

Even and Odd numbers Partition

Given an array A[], write a function to separate even and odd numbers (i.e., put all even numbers first than odd numbers) and stability is also maintain for the elements in the Array.

Eg.

input:

A[] = {12, 34, 45, 9, 8, 90, 3}   

output:                                
A[] = {12, 34, 8, 90, 45, 9, 3}  (OR)  {12 , 34,  90,  8,  9,  45,  3}

We can do it by using QuickSorting approach.But it requires one traversal across array elements.So it is O(n) approach.

private static void partitionArray(int[] a) {
  int i = 0;
  int j = a.length - 1;
  while (i < j) {
   while (a[i]%2==0)
    i++;
   while (a[j]%2==1)
    j--;

   if (i < j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    i++;
    j--;
   }
  }
 }

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

Reverse a line word by word AND swap two words in a given sentence

ex - my name is john
Then after reversing it will be like - john is name my

Method 1:

1. First scan the input string till midway and swap the first character with last and second character with second last and so on.

2. Second scan, swap the word within string the same way.


Problem II:
Swap two words in a given sentence
ex: my name is Khan in school.
swap name and in in the above sentence.
o/p : my in is name school.

Solution : 
Reverse the entire string  from starting word to ending word : Here starting word is name and ending word is in.So reverse the string from name to in using inplace string reversal algo.It requires O(n) traversal.
Step 1: 
Str = my name is Khan in school.
Str = my ni nahK si eman school
Step 2:
Now reverse the first word of the modifies string:
Str = my ni nahK si eman school
Str = my in nahk si eman school
Step 3 :
Now reverse the string after first word to second modified word.
Str = my in nahk si eman school
Str = my in is Khan eman school(after reversal)
Step 4 :
Now reverse the second word
Str = my in is Khan school
Str= my in is Khan name school

Original sentence         : my name is Khan in school.
After final modification : my in is Khan name school
Got the desired output.in and name are swapped in the given sentence.

Default Member variable values in java

There are several kinds of variables:

• Member variables in a class—these are called fields.
• Variables in a method or block of code—these are called local variables.
• Variables in method declarations—these are called parameters.

Automatic Initialization :

• Field variables (class members) are automatically initialized to default values
• Local variables (method or constructor variables) are not automatically initialized
• Arrays, whether field or local variables, are automatically initialized to the default values of their declared type

Refer : http://www.janeg.ca/scjp/lang/defaults.html

final class instance in method arguments

If we pass a final class instance variable?

public class Test {
 public static void main(String[] args) {
  TestObject test = new TestObject();
  modifyObjectName(test);
 }

 public static void modifyObjectName(final TestObject testObj) {
  System.out.println(testObj.getName());//first
  testObj.setName("name");
  System.out.println(testObj.getName());//name

testObj = new TestObject();//throw an error.Cannot modify final object reference
 }
}

public class TestObject {

 private String mName = "first";

 public void setName(String pName) {
  mName = pName;
 }

 public String getName() {
  return mName;
 }
}