package com.dw.algorithmlib;

import java.math.BigInteger;

public class MathHelper {
	
	// find gcd algorithm
	static int gcd(int a, int b) 
    { 
        if (a == 0) 
            return b; 
        return gcd(b % a, a); 
    } 
	
	static int findGCDInArray(int arr[], int n) 
    { 
        int result = arr[0]; 
        for (int i = 1; i < n; i++) 
            result = gcd(arr[i], result); 
  
        return result; 
    } 
	
    public boolean isSquare(int n) {
    	int t = (int)Math.sqrt(n);
    	
    	return t*t == n;
    }
    
    public static int charToInt(char c) {
    	return c - '0';
    }
    
    public boolean isPrime(int n) {
    	boolean result = true;
    	for(int i=2;i<=Math.sqrt(n);i++) {
    		if(n%i == 0) {
    			result = false;
    			break;
    		}
    	}
    	return result;
    }
    
    // @todo: add two large number using String
    // num1 = 12345678
    // num2 = 34567890
    public String add(String num1, String num2) {
    	int first = charToInt(num1.charAt(num1.length() - 1));
    	int second = charToInt(num2.charAt(num2.length() - 1));
    	
    	ListNode num1Head = new ListNode(first);
    	ListNode num2Head = new ListNode(second);
    	ListNode p1 = num1Head;
		for (int i = num1.length() - 2; i >= 0; i--) {
			ListNode t = new ListNode(charToInt(num1.charAt(i)));
			p1.next = t;
			p1 = t;
		}
		
		ListNode p2 = num2Head;
		for (int i = num2.length() - 2; i >= 0; i--) {
			ListNode t = new ListNode(charToInt(num2.charAt(i)));
			p2.next = t;
			p2 = t;
		}
		
		p1 = num1Head;
		p2 = num2Head;
		
		ListNode target = num1.length() > num2.length()? p1 : p2;
		ListNode targetHead = target;
		ListNode prevTarget = target;
		int carry = 0;
		while (p1 != null & p2 != null) {
			target.val = p1.val + p2.val + carry;
			carry = target.val/10;
			target.val = target.val % 10;
			p1 = p1.next;
			p2 = p2.next;
			prevTarget = target;
			target = num1.length() > num2.length()? p1 : p2;
		}
		
		if(carry != 0) {
			if(target != null) {
				target.val = target.val + carry;
			}
			else if(target == null) {
				ListNode newNode = new ListNode(carry);
				prevTarget.next = newNode;
			}
		}
		
		StringBuilder sb = new StringBuilder();
		
		p1 = targetHead;
		while(p1 != null) {
			sb.append(p1.val);
			p1 = p1.next;
		}
		
    	return sb.reverse().toString();
    }
    
    // @todo: multiply two large number using String
    public String Multiple(String num1, String num2) {
    	String result = "";
    	
    	return result;
    }
    
    // @todo: multiply two large number using String
    public String divide(String num1, String num2) {
    	String result = "";
    	
    	return result;
    }
	
    /**
     * Transfer number
     * @param N
     * @return
     */
	public String NumToMin2(int N) {
		if (N == 0)
			return "0";
		
		StringBuilder result = new StringBuilder();

		int temp;
		
		while (N != 0) {
	
			temp = N % (-2);
			N = (N - Math.abs(temp))/(-2);
	
			if (temp == 1) {
				result.append('1');
			} else
				result.append(temp == 0 ? '0' : '1');
	
		}
	
		return result.reverse().toString();
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BigInteger bi1, bi2, bi3;  
		
		 bi1 = new BigInteger("1200000000000000000000000000000000000000000");
	     bi2 = new BigInteger("50");

	      // perform add operation on bi1 using bi2
	      bi3 = bi1.gcd(bi2);
		  
	      String str = "Result of addition is " +bi3;;

	      // print bi3 value
	      System.out.println( str );
	}

}

@@ -639,24 +639,59 @@
 me(int n) %7B%0A
+    %09if (n%3C=1) return false;%0A    %09%0A
     %09boolean

fix isPrime function