Count all possible groups of size 2 or 3 that have sum as multiple of 3

Problem:
Given an unsorted integer (positive values only) array of size ‘n’, we can form a group of two or three, the group should be such that the sum of all elements in that group is a multiple of 3. Count all possible number of groups that can be generated in this way.

Input: arr[] = {3, 6, 7, 2, 9}
Output: 8
// Groups are {3,6}, {3,9}, {9,6}, {7,2}, {3,6,9},
//            {3,7,2}, {7,2,6}, {7,2,9}


Input: arr[] = {2, 1, 3, 4}
Output: 4
// Groups are {2,1}, {2,4}, {2,1,3}, {2,4,3}

Solution:

The idea is to see remainder of every element when divided by 3. A set of elements can form a group only if sun of their remainders is multiple of 3. Since the task is to enumerate groups, we count all elements with different remainders.

1. Hash all elements in a count array based on remainder, i.e, 
   for all elements a[i], do c[a[i]%3]++;
2. Now c[0] contains the number of elements which when divided
   by 3 leave remainder 0 and similarly c[1] for remainder 1 
   and c[2] for 2.
3. Now for group of 2, we have 2 possibilities
   a. 2 elements of remainder 0 group. Such possibilities are 
      c[0]*(c[0]-1)/2
   b. 1 element of remainder 1 and 1 from remainder 2 group
      Such groups are c[1]*c[2].
4. Now for group of 3,we have 4 possibilities
   a. 3 elements from remainder group 0.
      No. of such groups are c[0]C3
   b. 3 elements from remainder group 1.
      No. of such groups are c[1]C3
   c. 3 elements from remainder group 2.
      No. of such groups are c[2]C3
   d. 1 element from each of 3 groups. 
      No. of such groups are c[0]*c[1]*c[2].
5. Add all the groups in steps 3 and 4 to obtain the result.

// Returns count of all possible groups that can be formed from elements
// of a[].
int findgroups(int arr[], int n)
{
    // Create an array C[3] to store counts of elements with remainder
    // 0, 1 and 2.  c[i] would store count of elements with remainder i
    int c[3] = {0}, i;
 
    int res = 0; // To store the result
 
    // Count elements with remainder 0, 1 and 2
    for (i=0; i<n; i++)
        c[arr[i]%3]++;
 
    // Case 3.a: Count groups of size 2 from 0 remainder elements
    res += ((c[0]*(c[0]-1))>>1);
 
    // Case 3.b: Count groups of size 2 with one element with 1
    // remainder and other with 2 remainder
    res += c[1] * c[2];
 
    // Case 4.a: Count groups of size 3 with all 0 remainder elements
    res += (c[0] * (c[0]-1) * (c[0]-2))/6;
 
    // Case 4.b: Count groups of size 3 with all 1 remainder elements
    res += (c[1] * (c[1]-1) * (c[1]-2))/6;
 
    // Case 4.c: Count groups of size 3 with all 2 remainder elements
    res += ((c[2]*(c[2]-1)*(c[2]-2))/6);
 
    // Case 4.c: Count groups of size 3 with different remainders
    res += c[0]*c[1]*c[2];
 
    // Return total count stored in res
    return res;
}

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.geeksforgeeks.org/count-possible-groups-size-2-3-sum-multiple-3/

Jump game

Problem:
Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Solution:

bool canJump(int A[], int n) {
    int reach = 1;
    for (int i = 0; i < reach && reach < n; ++i)
        reach = max(reach, A[i] + i + 1);
    return reach >= n;
}

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://discuss.leetcode.com/questions/232/jump-game

Replace each element with its Next Larger Element on the right

Problem:
Given an Array, replace each element in the Array with its Next Element(To its RHS) which is Larger than it. If no such element exists, then no need to replace.
Ex:

i/p: {2,12,8,6,5,1,2,10,3,2}
o/p:{12,12,10,10,10,2,10,10,3,2}

Solution:

Naive solution is O(n^2) as it requires two nested loops.

A more optimal solution is to traverse the array from the right and put all elements in a BST, replacing each element in the array with its immediate in-order successor in the BST. This will take O(n log n) time to complete and require O(n) space.

The best solution also requires O(n) space but runs in O(n) time. We traverse the array from the left and keep pushing elements' indexes to a stack, ensuring that all the elements in the stack are always stored in decreasing order. Once the order is not decreasing, we pop the element from the stack (remember, it's an index) and replace the corresponding element in the array with an element currently being processed in the main loop:

void ReplaceNextLargest ( int * Arr, int N ) {
    stack<int> stk;
    stk.push(0);

    for( int idx = 1; idx < N; idx++ ) {
        while( !stk.empty() && (Arr[idx] > Arr[stk.top()]) ) {
            Arr[stk.top()] = Arr[idx];
            stk.pop();
        }
        stk.push(idx);
    }
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=6311825561878528
http://www.geeksforgeeks.org/next-greater-element/

Find number of ways to go n steps with 1 or 2 steps

Problem:
Frog can jump 1 or 2 steps write the code to find out number of ways to go up to n steps.

Solution:

The number of ways to jump to n steps is the n-th Fibonacci number!

F[n] = F[n-1] + F[n-2]; 
F1 = 1; F2 = 2;

Example:

F[3] = F[2] + F[1]
1 1 1 part of F[2]
2 1 part of F[2]
1 2 part of F[1]

F[2]
1 1 
2

F[1]
1

Complexity:

time - O(n)
space - O(1) (for iterative approach)

Links and credits:
http://www.careercup.com/question?id=5950229446656000

Inorder traversal of binary tree w/o recursion

Problem:
Inorder traversal of binary tree w/ recursion

Solution:

/* Iterative method using stack */
Inordertraversal(struct btree *root)   
{
 while(1)
 {   
  while( root )
  {
   push(root);
   root = root->left;
  }
  if(Isstackempty(S))
   return;
  printf( S(top)->data);
  root = pop(S);
  root = root->right;
 }
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=5198302274387968

Sort n numbers in range from 0 to n^2 – 1 in linear time

Problem:
Given an array of numbers of size n. It is also given that the array elements are in range from 0 to n2 – 1. Sort the given array in linear time.

Examples:
Since there are 5 elements, the elements can be from 0 to 24.
Input: arr[] = {0, 23, 14, 12, 9}
Output: arr[] = {0, 9, 12, 14, 23}

Since there are 3 elements, the elements can be from 0 to 8.
Input: arr[] = {7, 0, 2}
Output: arr[] = {0, 2, 7}

Solution:
The idea is to use Radix Sort. Following is standard Radix Sort algorithm.

Do following for each digit i where i varies from least significant digit to the most significant digit: Sort input array using counting sort (or any stable sort) according to the i’th digit.

Let there be d digits in input integers. Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers, for example, for decimal system, b is 10. Since n2-1 is the maximum possible value, the value of d would be O(\log_b(n)). So overall time complexity is O((n+b)*\log_b(n)). Which looks more than the time complexity of comparison based sorting algorithms for a large k. The idea is to change base b. If we set b as n, the value of O(\log_b(n)) becomes O(1) and overall time complexity becomes O(n).

arr[] = {0, 10, 13, 12, 7}

Let us consider the elements in base 5. For example 13 in
base 5 is 23, and 7 in base 5 is 12.
arr[] = {00(0), 20(10), 23(13), 22(12), 12(7)}

After first iteration (Sorting according to the last digit in 
base 5),  we get.
arr[] = {00(0), 20(10), 12(7), 22(12), 23(13)}

After second iteration, we get
arr[] = {00(0), 12(7), 20(10), 22(12), 23(13)}

How to sort if range is from 1 to n2?
If range is from 1 to n n2, the above process can not be directly applied, it must be changed. Consider n = 100 and range from 1 to 10000. Since the base is 100, a digit must be from 0 to 99 and there should be 2 digits in the numbers. But the number 10000 has more than 2 digits. So to sort numbers in a range from 1 to n2, we can use following process.
1) Subtract all numbers by 1.
2) Since the range is now 0 to n2, do counting sort twice as done in the above implementation.
3) After the elements are sorted, add 1 to all numbers to obtain the original numbers.

How to sort if range is from 0 to n^3 -1?
Since there can be 3 digits in base n, we need to call counting sort 3 times.


PS. Note: the counting sort for the radix sort for base n requires O(n) memory. We could try to use a bit-set for sorting if all the numbers are unique.

Complexity:

time - O(n)
space - O(n) (for counting sort)

Links and credits:
http://www.geeksforgeeks.org/sort-n-numbers-range-0-n2-1-linear-time/