Practice

Greatest Common Divisor

Given 2 non negative integers m and n, find gcd(m, n)

GCD of 2 integers m and n is defined as the greatest integer g such that g is a divisor of both m and n.
Both m and n fit in a 32 bit signed integer.

Example

m : 6
n : 9

GCD(m, n) : 3

NOTE : DO NOT USE LIBRARY FUNCTIONS

public class Solution {
    public int gcd(int A, int B) {
        if (A == B) {
            return A;
        }
        if (B == 0 || A == 0) {
            return 1;
        }
        
        if (A > B) {
            int temp = A;
            A = B;
            B = temp;
        }
        
        ArrayList<Integer> AFactories = new ArrayList<>();
        for (int i = 1; i <= A; i++) {
            if (A%i == 0) {
                AFactories.add(i);
            }
        }
        
        for (int i = AFactories.size() - 1; i >= 0; i--) {
            if (B%AFactories.get(i) == 0) {
                return AFactories.get(i);
            }
        }
        return 1;
    }
}

Rearrange Array

Rearrange a given array so that Arr[i] becomes Arr[Arr[i]] with O(1) extra space.

Example:

1 2	Input : [1, 0] Return : [0, 1]

Lets say N = size of the array. Then, following holds true :

All elements in the array are in the range [0, N-1]

N * N does not overflow for a signed integer

public class Solution {
    public void arrange(ArrayList<Integer> a) {
        int n = a.size();
        for (int i = 0; i < n; i++) {
            int v = a.get(i);
            int w = a.get(v) % n;
            int x = v + w * n;
            a.set(i, x);
        }
        for (int i = 0; i < n; i++) {
            int v = a.get(i);
            a.set(i, v/n);
        }
    }
}

Palindrome Integer

Determine whether an integer is a palindrome. Do this without extra space.

A palindrome integer is an integer x for which reverse(x) = x where reverse(x) is x with its digit reversed.
Negative numbers are not palindromic.

Example :

Input : 12121
Output : True

Input : 123
Output : False

public class Solution {
	public boolean isPalindrome(int a) {
	    if(a == check(a))
	        return true;
	    else
	        return false;
	}
	
	public int check(int num){
        int reverted = 0;
        while (num > 0) {
            reverted = reverted*10 + num%10;
            num /= 10;
        }
      return reverted;
	}
}