merlinparrajimenez
BAN USER- -1of 1 vote
AnswersI was asked the following: Given integers N and A. Find how many integer sequences with elements between 1 and A have sum of all elements equals to N.
- merlinparrajimenez in United States
N, A <= 1000.
Sample input: 4 3 , sample output is 7.
In this moment, I realized I do not understand the question. If I have a sequence of 1,2,3, the only sub-sequence that sums 4 is 1,3. So the answer should be 1. What am I missing?
Thank you| Report Duplicate | Flag | PURGE
Algorithm Arrays
@Anonymous on January 19, 2011
Find any duplicate in a sorted list is O(n). Example, 1,2,3,4,5,6,7,8,9,9
you have to iterate all the list, in the worse case, to figure it out.
your answer is O(n^2) but it can be done in O(n) using a hash. So, you wont check if the character is the string 'result', just validate if it is already a key in the hash
- merlinparrajimenez January 18, 2014In Java (there is no need for an additional array):
public static void main(String[] args) {
int A[] = { 1, 3, 5, 6, 9 };
int B[] = new int[12];
B[0] = 3;
B[1] = 6;
B[2] = 8;
B[3] = 10;
B[4] = 11;
B[5] = 13;
B[6] = 15;
mergeInB(A, B, 7);
for (int n : B)
System.out.print(n + " ");
}
/**
* @param a
* @param b - it will be modified
* @param j = length of b
*/
public static void mergeInB(int[] a, int[] b, int j) {
int i = a.length - 1, k;
j --;
for (k = b.length-1; k >= 0; k--) {
if (i >= 0 && j >= 0) {
if (a[i] > b[j]) {
b[k] = a[i];
i --;
}
else
{
b[k] = b[j];
j --;
}
}
else break;
}
while(i>=0 && k >=0) {
b[k] = a[i];
k --;
i --;
}
while(j>= 0 && k >=0) {
b[k] = b[j];
j--;
k--;
}
}
I did not understand very well.
- merlinparrajimenez January 18, 2014If child node > parent node && parent node = 0, then swap values.
But the child node has children with values larger than 0. So, is the idea to swap recursively by levels?
Could you write an example, please?