Algorithm - Numbers
Bitwise Manipulation
Bitwise operators include ~(NOT), | (OR), & (AND), and ^ (XOR).
^: If the bits are the same, the result is 0. If the bits are different, the result is 1.
Left shift and right shift operation.
Left shift and right shift operation.
Use & to do modular operation, for instance: int & 0x1F means mod 32.
Optimizing with Shifts
The shift operators enable you to multiply and divide by powers of 2 very quickly.
Swap X and Y
x = x^y; y=x^y; x=x^y;
Number of Ones
Write a function that determines the number of 1 bit in the computer's internal representation of a given integer.
public static int numOnesInBinary(int number) {
int numOnes = 0;
while (number != 0) {
if ((number & 1) == 1)
numOnes++;
number = number >>> 1;
}
return numOnes;
}
This is O(n), where n is the size of bits.
Theory:
Consider what happens at the bit level when you subtract 1 from a number. Subtracting 1 produces a value that has all the same bits as the original integer except that all the low bits up to and including the lowest 1 are flipped.
If you apply the AND operation to the integer and the result of the subtraction, the result is a new number that is the same as the original integer except that the rightmost 1 is now a 0.
public static int numOnesInBinary(int number) {
int numOnes = 0;
while (number != 0) {
number = number & (number - 1);
numOnes++;
}
return numOnes;
}
This solution has a running time of O(m), where m is the number of 1's in the solution.
Or for integer limited in small bits, we can use space-time tradeoff algorithm, write a array to store the answer - number of one in bits, the complexity of this algorithm is O(1).
For two positive integers A, B(binary-coded), how many bits we have to change in order to convert A to B?
public static int bitsChangeNeededFromAtoB(int a, int b)
{
int c = a ^ b;
return numOnesInBinary(c);
}
In the decimal representation of N!, how many zeros there are at the end? For example, 10!=3 628 800, so the answer is 2.
This is to find out how many 5s and 2s in the product because a 5 and a 2 makes a 10 where you get a zero per pair. Because the number of 2s is sure to be much greater than that of 5s,this problem is to figure out how many 5s in the numbers from 1 to N.
public static int numZerosInEndofOfFactoriaN(int n)
{
int result = 0;
int i, j;
for(i=1; i<=n; i++)
{
j=i;
while(j%5==0)
{
result++;
j/=5;
}
}
return result;
}
This question can continue to simplify to figure out the number z = [N/5] +[N/(5*5)] +[N/(5*5*5)] + ...
This is because each factor of 5 contributes one zero, and 25's contribute 2 factors of 5, contribute one more factor of 5.
public static int numZerosInEndofFactoriaN(int n) {
int result = 0;
while(n>0)
{
result += n/5;
n /=5;
}
return result;
}
Then in the binary-coded representation of N!, how many zeros there are at the end? For example, 3!= 6 = 1010, so the answer is 1.
This question is same as to figure out how many prime factors of 2 in factorial n.
A = [N/2] +[N/(2*2)] +[N/(2*2*2)] + ...
public static int numZerosInEndOfBinaryofFactoriaN(int n) {
int result = 0;
while (n > 0) {
n >>= 1;
result += n;
}
return result;
}
This tech can be used to find out many prime factors of x in factorial of n.
For a number n, figure out whether it is power of 2.
This is to find out in binary-coded representation of n, whether there are only one bit is 1, and the 1 is not at the last, whether x&(x-1)=0
public static boolean powerof2(int n) {
boolean result = false;
if (n > 0) {
if ((n & (n - 1)) == 0)
result = true;
}
return result;
}
Q. Determine the number of bits required to convert integer A to integer B.
xor A and B, Each 1 in the xor will represent one different bit between A and B.
Q. Swap odd and even bits in an integer with as few instructions as possible.
public static int swapOddEvenBits(int x) {
return ( ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1) );
}
Q. Give two 32-bit numbers, N and M, and two bit positions i and j(i<j), a="" all="" and="" between="" bits="" equal="" i="" in="" j="" m.<="" method="" n="" set="" span="" to="" write="">
1. Clear all bits in N between position i and j
2. ORing to put M in there.
public static int updateBits(int n, int m, int i, int j) {
int max = ~0; /* All 1’s */
// 1’s through position j, then 0’s
int left = max - ((1 << j) - 1);
// 1’s after position i
int right = ((1 << i) - 1);
// 1’s, with 0s between i and j
int mask = left | right;
// Clear i through j, then put m in there
return (n & mask) | (m << i);
}
public static String printBinary(String n)
{
int intPart = Integer.parseInt(n.substring(0, n.indexOf('.')));
double decPart = Double.parseDouble(n.substring(n.indexOf('.'), n.length()));
String int_string = "";
while (intPart > 0)
{
int r = intPart % 2;
intPart >>= 1;
int_string = r + int_string;
}
StringBuffer dec_string = new StringBuffer();
while (decPart > 0)
{
if (dec_string.length() > 32) return "ERROR";
if (decPart == 1)
{ dec_string.append((int) decPart); break;}
double r = decPart * 2;
if (r >= 1)
{ dec_string.append(1); decPart = r - 1;}
else
{ dec_string.append(0); decPart = r; }
}
return int_string + "." + dec_string.toString();
}
Q. An array A[1..n] contains all the integers from 0 to n except for one number which is missing. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jth bit of A[i]".
Thoery: balance of 1s and 0s in the least signifcant bit.
int fndMissing(ArrayList<BitInteger> array) {
return fndMissing(array, BitInteger.INTEGER_SIZE - 1);
}
int fndMissing(ArrayList<BitInteger> input, int column) {
if (column < 0) { // Base case and error condition
return 0;
}
ArrayList<BitInteger> oddIndices = new ArrayList<BitInteger>();
ArrayList<BitInteger> evenIndices = new ArrayList<BitInteger>();
for (BitInteger t : input) {
if (t.fetch(column) == 0) {
evenIndices.add(t);
} else {
oddIndices.add(t);
}
}
if (oddIndices.size() >= evenIndices.size()) {
return (fndMissing(evenIndices, column - 1)) << 1 | 0;
} else {
return (fndMissing(oddIndices, column - 1)) << 1 | 1;
}
}
Q. Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.
To get the next number:
1 Traverse from right to left. Once we’ve passed a 1, turn on the next 0.
2 Turn of the one that’s just to the right side of that.
3 Make the number as small as possible by rearranging all the 1s to be as far right as possible.
To get the previous number, we do the reverse:
1 Traverse from right to left. Once we’ve passed a zero, turn of the next 1.
2 Turn on the 0 that is directly to the right.
3 Make the number as big as possible by shifting all the ones as far to the left as possible.
Numbers Related Algorithms Questions
Greatest Common Divisor
gcd(a,b)=gcd(a-b,b)=gcd(b,a%b)
gcd(a,b) = gcd(|a|,|b|)
public static long gcd( long a, long b )
{
if(a<0) a=-a;
if(b<0) b=-b;
if(a<b)
{
a=a^b;
b=a^b;
a=a^a;
}
return gcdImp(a,b);
}
private static long gcdImp( long a, long b )
{
if( b == 0 )
return a;
else
return gcd( b, a % b );
}
Modular arithmetic
1. If A(mod N) = B(mod N), then for any C, (A+C)(mod N) = (B+C)(mod N), (AC)(mod N) = (BC)(mod N), (A^C)(mod N) = (B^C)(mod N).
Compuete the last digit in 3333^5555 = 3333^5555 (mod 10) = (3333 mod 10) ^5555(mod 10) = 3^5555(mod 10)
3^4 mod 10 = 1, so 3^ (4^1388) = 1, so 3^5555(mod 10)= 3^3 mod 10 = 7
Exponentiation - X^N
If N is even, X^N = (X*X)^(N/2) else X^N = X*(X*X)^(N/2).
Based on this, we can compute X^N in O(logN)
Modular Exponentiation - X^N mod p
If N is even, X^N = (X*X mod p)^(N/2) mod p else X^N = {X*[(X*X mod p)^(N/2) mod p]} mod p.
public static long power(long x, long n, long p)
{
return doPower(x % p, n, p);
}
public static long doPower(long x, long n, long p)
{
if (n == 0) return 1;
long tmp = doPower((x * x) % p, n / 2, p);
if (n % 2 != 0) tmp = (tmp * x) % p;
return tmp;
}
Find Nth fibonacci number in O(logN) time complexity.
A* [ F(n) F(n-1) ] = [ F(n+1) F(n) ]
A* [ F(n) F(n-1) ] = [ F(n+1) F(n) ] = A^n * [ F(1) F(0) ]
To find A^n, we can do R = A^(n/2) * A^(n/2) and if n is odd, we need do multiply with an A at the end.
Numbers are randomly generated and stored into an expanding array.
Q1. How to keep track of the median?
Maintain two heaps, the smallest half is kept in a max heap, contaning the smallest half of the elements, the biggest half is kept in a min heap. With these data structures, you have the potential median elements at the roots. If the heaps are no longer the same size, rebalance the heaps by popping an element of the one heap and pushing it onto the other.
Q2. How to find the kth largest element? (Same as above)
Q. Find out all primes between 1 and n.
void gen_primes(int max)
{
int[] primes = new int[max];
int i, j;
for (i = 0; i < max; i++)
primes[i] = 1;
for (i = 2; i <= (int) Math.sqrt(max); i++)
if (primes[i] == 1) for (j = i; j * i < max; j++)
primes[i * j] = 0;
// i is prime if primes[i] is still 1.
}
Q. Goldbach's Conjecture:
For any integer n (n ≥ 4) there exist two prime numbers p1 and p2 such that p1 + p2 = n. In a problem we might need to find the number of essentially different pairs (p1, p2).
int FindSol(int n)
{
int i,res=0;
for(i=2;i<=n/2;i++)
if (primes[i] && primes[n-i]) res++;
}
Q. Shuffle an array
public static void shuffleArray(int[] a) {
int n = a.length;
Random random = new Random();
random.nextInt();
for (int i = 0; i < n; i++) {
int change = i + random.nextInt(n - i);
swap(a, i, change);
}
}
Key point - int change = i + random.nextInt(n - i); swap(a, i, change);
Endianness
Endianness refers to the order in which a computer stores the bytes of a multibyte value.
In a big-endian machine the MSB has the lowest address; in a little-endian machine the
LSB has the lowest address.
JAVA virtual machine always used big-endian, Intel x86 used little-endian.
Java code to detect os endianness:
ByteOrder b = ByteOrder.nativeOrder();
if(b.equals(ByteOrder.BIG_ENDIAN)) { System.out.println("Big-endian"); }
else { System.out.println("Little-endian"); }
C code:
Resources
bool isLitteEndian(){
int testNum;
char *ptr;
testNum = 1;
ptr = (char *) &testNum;
return (*ptr); /* Returns the byte at the lowest address */
}
bool isLitteEndian(){
union {
int theInteger;
char singleByte;
} endianTest;
endianTest.theInteger = 1;
return endianTest.singleByte;
}
public final static int swabInt(int v) {
return (v >>> 24) | (v << 24) |
((v << 8) & 0x00FF0000) | ((v >> 8) & 0x0000FF00);
}
Resources
