Weighing Puzzle

Problem Statement:

You are given n(<=8) weights, w1,w2, · · · ,wn. Find all distinct weight measurements that you can make using a common balance and the given weights. For example, assume that you are given weights of 1, 3, and 5 units. You can weigh all measures from 1 to 9 units as:

•1=1 2=3−1
•3=3 4=3+1
•5=5 6=5+1
•7=5+3−1 8=5+3
•9=5+3+1

You can subtract a specific weight you have, by adding it along with item to be measured.
Your input will contain the number of weights you have, followed by the weights themselves.
You need to output all the possible weights you can measure in the increasing order.
You should not repeat any measures.

Input: First Line contains N(number of distinct weights)(N<=8). Next line will have N distinct weights separated by space.
 
Output: list of distinct weights possible in increasing order followed by ‘\n’.

Code in C++:

Kadane's Algorithm: 2D Array

Code:

Time complexity: O(n^3)

Finding pair of elements with maximum XOR from the array

Problem Statement:

Given an integer array A[1..N], find max value of A[i]^A[j] , where ^ is bitwise xor.
Input:
First Line contains N (1 < N <= 100000)
second line contains N non-negative integers seperated by space.(value of integer is < 32000)
Output:
Print the answer in a single line, followed by a '\n' ( just print a new line, no need to display '\n' ).
Sample Test Case:
Input:
5
1 10 20 30 40
Output:
60
Explanation:
XOR ing of 20 and 40 equals to 60, which is maximum of XOR ing of all other pairs.
 
Approach:

A data structure named trie is very useful for solving this problem. All we have to do is to construct a tree of binary representation of the numbers in the array and keep looking for 01-10 and 00-11 pairs. In case both 01-10 and 00-11 branches are encountered at the same level of the tree, compute the XOR for both the branches and select the maximum among them.

Code in C++:

Weird Function problem from Spoj

Problem statement:
Let us define :
F[1] = 1
F[i] = (a*M[i] + b*i + c)%1000000007 for i > 1

where M[i] is the median of the array {F[1],F[2],..,F[i-1]}.
The median of an array is the middle element of that array when it is sorted. If there are an even number of elements in the array, we choose the first of the middle two elements to be the median.

Given a,b,c and n, calculate the sum F[1] + F[2] + .. + F[n].

Input

The first line contains T the number of test cases. Each of the next T lines contain 4 integers : a,b,c and n.

Output

Output T lines, one for each test case, containing the required sum.

Example

Sample Input :
2
1 0 0 3
3 1 2 6

Sample Output :
3
103

Constraints

1 <= T <= 100
0 <= a,b,c < 1000000007
1 <= n <= 200000

Code in C++:

Lowest Common Ancestor (LCA) Problem

Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).

The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from v to w can be computed as the distance from the root to v, plus the distance from the root to w, minus twice the distance from the root to their lowest common ancestor.

Algorithm:
As we trace the two paths from both nodes up to the root, eventually it will merge into one single path. The LCA is the exact first intersection node where both paths merged into a single path. An easy solution is to use a hash table which records visited nodes as we trace both paths up to the root. Once we reached the first node which is already marked as visited, we immediately return that node as the LCA.

Problem:
Input:
No. of nodes in the binary tree
Preorder traversal of the tree
Inorder traversal of the tree
No. of queries
Node1 Node2
.
.
.


Output:
LCA of Node1 and Node2

Code in C++:




Time complexity: O(nq) (n: no.of nodes, q: no. of queries)

Maximum Subarray Problem

Maximum Subarray Problem:
The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

Let us solve this problem step-by-step. The naive and simplest brute-force solution would be to consider each index of the array as the start of the subarray and checking if the sum till each of the further indices in the array is maximum. Assuming n to be the size of the array, we will iterate through the array n times to fix the start i of the subarray and for each of these n start indices, we will iterate n-i times through the array for finding the end index of the maximum sum subarray. Hence, the time complexity of the solution will be: O(n^2).

Algorithm: 

def max_subarray(A, n):

    left = right = 0

    max_sum = -INF

    for i = 0 to n:

        sum = 0

        for j = i to n:

            sum = sum + A[i]

            if sum > max_sum:

               max_sum = sum

               left = i

               right = j

    return (left, right, max_sum)

Code in C++:

Algorithm:

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Code in C++:

 

Time Complexity: O(n)