Sean
BAN USERElegant solution, but checks 'start < arr.length -1' and 'end > 0' should be before arr[start] and arr[end] respectively. That is, the while statement should have looked like below -
while (start < arr.length - 1 && arr[start] != 0)
start++;
while (end > 0 && arr[end] == 0)
end--;
/**
*
* Assumption :
* +123.40 , where + sign appears before the number is valid
* 146. , where no digits after point is not a valid number
*
* For a string to be a number, it should be of the format
*
* [0 or 1 occurrence of either + or -]
* followed by
* [at least one occurrence of digits between 0 to 9]
* followed by
* [0 or 1 occurrence of .]
* followed by
* [at least one occurrence of numbers between 0 to 9]
*
* [+|-] means either + or -
* [+|-]? means either + or - should occur once or not at all
* \d means a digit. To escape the backslash, you need \\d
* \\d+ means a digit should occur atleast once
* .? means that a should occur or not at all
* \\d+ means a digit should occur atleast once
*/
public class IsStringANumber {
public static boolean isANumber(String str) {
if (str == null || str.trim().equals(""))
return false;
return Pattern.matches("[+|-]?\\d+.?\\d+", str);
}
}
Since S is { 0, 1, 2, ..., ( (2^k) - 1 ) } the way i understand the questions is,
- Sean January 12, 2016if k is 2 then S is { 0, 1, 2, 3 }
if k is 3 then S is { 0, 1, 2, 3, 4, 5, 6, 7 }
Observations:
(1) Set S contains 2^k integers
(2) k bits required to represent the last number
(3) there are k distinct numbers in set S where all the least significant bits are 1's. For example, when k=3, they are 1(001), 3 (011), 7 (111)
(4) numbers listed in observation (3) will be of the form (2^i) -1 where 1 <= i <= k
(5) there will be (2^i)-1 numbers in S that are less than the number (2^i)-1 mentioned in observation (4). For example, for i = 2 the numbers will be 0, 1, and 2.
To satisfy the first condition, which is a < b, for any given number b in S we need to look all the numbers a that are less than it. In other words number of bits used to represent a will be less than or equal to b. For example if b is 3, then we need to look at combinations (0,1), (0,2), (0,3), (1,2), (1,3), (2,3).
To satisfy second condition, which is (a AND b) == a, b should be all 1's. This is because 0 AND 1 is 0. 1 AND 1 is 1. So ANDing with 1 will retain whatever the other bit is. From observation (3) we see that there are k such numbers in S. The possibilities for number b can be any of these k numbers. The possibility for a is any number that is less than b. That is for k = 3, b can be either 1, 3, 7. The corresponding a’s have to be less that, making the complete set as below -
Possibilities when b = 1 are (0, 1)
Possibilities when b = 3 are (0, 3) (1, 3) (2, 3)
Possibilities when b = 7 are (0, 7) (1, 7) (2, 7) (3, 7) (4, 7) (5, 7) (6, 7)
Based on observation (5),
Possibilities when b = 1 are 1
Possibilities when b = 3 are 3
Possibilities when b = 7 are 7
Possibilities when b = (2^k)-1 are (2^k)-1
Adding them all together we get a series like
1 + 3 + 7 + … + ((2^k) - 1)
i.e. ((2^1) - 1) + ((2^2) - 1) + ((2^3) - 1) + … + ((2^k) - 1)
i.e. (2^1) + (2^2) + (2^3) + (2^k) - k { geometric series }
i.e. (2^(k+1)) - 3 - k
To summarize, we can say that for a given k (where k > 0) and S of the form { 0, 1, 2, 3, … , ( (2^k) - 1 ) } the number of pairs a, b that satisfy the conditions a < b ; ( a AND b ) == b will be (2^(k+1)) - 2 - k
Lets verify for few :
k = 3 : 11 : (0, 1), (0, 3) (1, 3) (2, 3), (0, 7) (1, 7) (2, 7) (3, 7) (4, 7) (5, 7) (6, 7)
k = 2 : 4 : (0, 1), (0, 3) (1, 3) (2, 3)
k = 1 : 1 : (0, 1)