brijpal.ism
BAN USERRate of increase (ROI) of index is exactly one. Rate of increase value at any index is always greater then or equal to one. Hence, ROI of value is greater then or equal to ROI of index.
Start value of index is 1.
If we start with index value 1 and keep increasing index by 1 and check
1) if A[index]=index we found the value. Stop checking
2) if A[index] = NOT_FOUND, value could not be found stop checking
3) if A[index]>index then index value is became greater then index and since ROI of value is greater then or equal ROI of index. So the condition A[index]=index would never come. Stop checking.
This algorithm find value in O(n) time complexity.
We can reduce this time complexity to O(log n) by carefully changing the logic and use concept o binary search. To accomplish this, increase index by multiplying it by 2 and check. Before increasing next index record the previous index too. Pseudo code could be like
int startIndex = 1;
int endIndex = startIndex * 2;
while (true) {
indexedValue = array[endIndex];
if (indexValue == NOT_FOUND) {
return NOT_FOUND;
}
int index = endIndex;
if (index == indexedValue) {
return indexedValue)
} else if (index < indexedValue) {
//value can be found in between startIndex and endIndex only. Find it in usual way exactly like binary search
} else {
//value can be found only be found in next part of array only
startIndex = endIndex;
endIndex = endIndex * 2;
}
}
I may not understand the question properly. I think following java code can solve this problem.
public static String toBinaryString(int k) {
if (k == 1) {
return String.valueOf(k);
} else {
return toBinaryString(k / 2) + k % 2;
}
}
Please correct and help me solve it out.
Here is working java code based on "reverse string and then reverse each word". It runs in O(1) space and O(n) time complexity.
public static String reverseWords(String str) {
char[] array = str.toCharArray();
reverseChar(array, 0, array.length);
int start = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == ' ') {
reverseChar(array, start, i);
start = i + 1;
}
}
//Now reverser the final word
reverseChar(array, start, array.length);
return new String(array);
}
private static void reverseChar(char[] array, int startPos, int endPos) {
int size = endPos - startPos;
if (size <= 0) {
throw new IllegalArgumentException("Size can not be " + size);
}
int mid = startPos + (size >> 1);
int lastIndex = endPos - 1;
for (int i = startPos; i < mid; i++) {
char temp = array[i];
array[i] = array[lastIndex];
array[lastIndex--] = temp;
}
}
public class FullName {
private String firstname;
private String lastname;
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result
+ ((firstname == null) ? 0 : firstname.hashCode());
result = prime * result
+ ((lastname == null) ? 0 : lastname.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof FullName)) {
return false;
}
final FullName other = (FullName) obj;
if (firstname == null) {
if (other.firstname != null)
return false;
} else if (!firstname.equals(other.firstname))
return false;
if (lastname == null) {
if (other.lastname != null)
return false;
} else if (!lastname.equals(other.lastname))
return false;
return true;
}
}
Just putting example to make it clearer
final int x = -Integer.MAX_VALUE;
System.out.println(Integer.toBinaryString(x)); // prints 10000000000000000000000000000001
System.out.println(Integer.toBinaryString(x>>1)); // prints 11000000000000000000000000000000
System.out.println(Integer.toBinaryString(x>>>1)); // prints 01000000000000000000000000000000
java class to implement above logic
- brijpal.ism April 23, 2010public class BinarySearchInStream {
private static final Integer NOT_FOUND = null;
public static void main(String[] args) {
int[] array = { -100, -13, -3, 4 };
System.out.println(findIndexValue(array));
}
private static Integer findIndexValue(int[] array) {
int startIndex = 1;
int endIndex = startIndex << 1;
while (true) {
Integer indexValue = get(array, endIndex);
if (indexValue == NOT_FOUND) {
return NOT_FOUND;
}
int index = endIndex;
int indexedValue = indexValue.intValue();
if (index == indexedValue) {
return indexValue;
} else if (index < indexedValue) {
return findIndexedValue(array, startIndex, endIndex);
} else {
startIndex = endIndex;
endIndex = endIndex << 1;
}
}
}
private static Integer get(int[] array, int index) {
try {
return array[index - 1];
} catch (ArrayIndexOutOfBoundsException e) {
return NOT_FOUND;
}
}
private static Integer findIndexedValue(int[] array, int startIndex,
int endIndex) {
int mid = (endIndex - startIndex) >> 1;
mid += startIndex;
Integer i = get(array, mid);
if (i == NOT_FOUND) {
return NOT_FOUND;
}
int value = i.intValue();
if (value == mid) {
return mid;
} else if (mid > value) {
return findIndexedValue(array, mid + 1, endIndex);
} else if (mid < value) {
return findIndexedValue(array, startIndex, mid - 1);
}
return NOT_FOUND;
}
}