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.

Count the number of numbers up to n which are both square and cube

Count the number of numbers up to n which are both square and cube.
e.g., for 1 < n < 1000 answer is 2 (64, 729)

The numbers 0 and 1 are self-squares and self-cubes, all exponentials being 0 and 1 respectively. Only a few other numbers are both squares and cubes of integers.

For any given square and cube, the numerical relation is n3 = [n(sqrt n)]2
so for the value n where (sqrt n) is whole number, the cube of n is also a square.
After 0 and 1, the next 4 are 64, 729, 4096, and 15625.

64 = 43 = 82 . (4x2)2
729 = 93 = 272 . (9x3)2
4096 = 163= 642 . (16x4)2
15625 = 253 = 1252 . (25x5)2

You can find the others easily. There are each the sixth power of any integer,
such that x6 = (x2)3 = (x3)2 e.g. 26 = 64, 36 = 729, 46 = 4096, etc. - Besides 64, another easy one is the number one million, 106, which is 1003 and 10002.

We can say that these numbers are the cube of a square, or the square of a cube, for any given integer.

Average of a stream of numbers

Given a stream of numbers, print average (or mean) of the stream at every point. For example, let us consider the stream as 10, 20, 30, 40, 50, 60, …

  Average of 1 numbers is 10.00
  Average of 2 numbers is 15.00
  Average of 3 numbers is 20.00
  Average of 4 numbers is 25.00
  Average of 5 numbers is 30.00
  Average of 6 numbers is 35.00
  ..................

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

Dynamic programming

Here is a link points to important resources of dynamic programming :
http://avidullu.wordpress.com/2010/02/18/solution-to-dynamic-programming-problems/

Medals puzzle

In a sports contest there were m medals awarded on n successive days (n > 1).
1. On the first day 1 medal and 1/7 of the remaining m - 1 medals were awarded.
2. On the second day 2 medals and 1/7 of the now remaining medals was  awarded; and so on.
3. On the nth and last day, the remaining n medals were awarded.

How many days did the contest last, and how many medals were awarded  altogether?


Total 36 medals were awarded and the contest was for 6 days.
On day 1: Medals awarded = (1 + 35/7) = 6 : Remaining 30 medals
On day 2: Medals awarded = (2 + 28/7) = 6 : Remaining 24 medals
On day 3: Medals awarded = (3 + 21/7) = 6 : Remaining 18 medals
On day 4: Medals awarded = (4 + 14/7) = 6 : Remaining 12 medals
On day 5: Medals awarded = (5 +7/7) = 6 : Remaining 6 medals
On day 6: Medals awarded 6

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);
 }
}

Maximum number of nested envelopes

You are given an unlimited number of each of n different types of envelopes. The dimensions of envelope type i are xi × yi. In nesting envelopes inside one another, you can place envelope A inside envelope B if and only if the dimensions A are strictly smaller than the dimensions of B.


Algorithm to determine the largest number of envelopes that can be nested inside one another.?

Solution:
1. Sort all the xi's in ascending order -> nlog(n)
2. Then find the longest increasing sequence of yi's -> nlog(n) 
3. complexity will be nlog(n).