epavlova
BAN USERCouldn't be problem attacked in the following way? :
There are N levels by M nodes each( for simplicity now I ignore source and sink levels ). So we have 2 ^ N - 1 possible ways to find a way between first and last level (no taking into account when path go only through nodes sink and source). For each combination of levels L, there are M^K ways to get node, where K is count of all set bits in L.So number of ways between first and last level would be : for (int l = 1; l< 2^n ;l++) sum+=m^k; where k is number of set bits in l. We now have to take into account sink and source nodes , which provides us addtional ways - > m^2*sum + 1 if n > 1 or m+1 if n = 1- this
Here is my solution
int numberOfPairs(int[] data, int n) {
if (data == null)
throw new NullPointerException();
int count = 0;
int backPointer = data.length - 1;
for (int index = 0; index <backPointer;) {
if ((data[backPointer] + data[index] >= n)) {
count+=backPointer - index ;
System.out.println(data[backPointer] +" "+ data[index]);
backPointer--;
} else
index++;
}
return count;
}
I think the following solution. Let's split the array in two sets - one that contains elements lower than N [0-N) and other that contains elements greater or equal to N [N,2N-1)
- epavlova September 24, 2015I reorder two sets one after another for the reason to sort each of the sets and iterate all numbers from 0 to 2*N - 1 to print absent elements. Time complexity is O(n) and space complexity o(1)
{{
void swap (int i, int j, int[] data) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
void findCountInSplit(int[] numbers, int N, boolean lessThanN) {
int index = 0 ;
while (index < numbers.length) {
if (lessThanN) {
if ((numbers[index] < N) && (numbers[index] != index))
swap(index, numbers[index], numbers);
else
index++;
} else {
if ((numbers[index] >= N) && (numbers[numbers[index]-N] != numbers[index]))
swap(index, numbers[index] - N, numbers);
else
index++;
}
}
int upperBound = 0;
int lowerBound = 0;
if (lessThanN) {
upperBound = N;
lowerBound = 0;
}
else {
upperBound = 2*N;
lowerBound = N;
}
for (index = lowerBound ; index < upperBound; index ++) {
if (lessThanN) {
if((numbers[index] >= N)){
System.out.print(index +" ");
}
} else {
if((numbers[index - N] < N)){
System.out.print(index +" ");
}
}
}
}
void printAbsentNumbers(int[] numbers) {
int N = numbers.length;
for (int element : numbers) {
if ((element < 0) || (element > (2 * N - 1)))
throw new IllegalArgumentException();
}
findCountInSplit(numbers,N, true);
findCountInSplit(numbers,N, false);
for(int t:numbers ){
System.out.print(t);
}
}
}}