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++: