A general add K-nary with explanation


  • 1
    O

    How will a programmer implement a method that can destroy the earth?

    A method called destroyEarth() is generally a bad practice, instead, I believe all programmers prefer implementing a destroyPlanet(Planet planet) method and use earth as input, so that code reuse/code extensibility/testability is addressed.

    So does this implementation for add binary. The key point here is for any k-nary add, the method for calculating remaining value and carry-on value is the same. For each digit, the remaining value is sum of two digits from two numbers minus K, and the carrying on value only depends on whether the sum is larger than K. Then this implementation is intuitive.

    More refactoring can be done, though.

    class Solution {
        public String addBinary(String a, String b) {
            return addKnary(a, b, 2);
        }
        
        public String addKnary(String a, String b, int k) {
    		// Make sure a.length() <= b.length()
    		if(a.length() > b.length()) return addKnary(b, a, k);
    		
    		int carry = 0;
    		int offset = b.length() - a.length();
    		StringBuilder result = new StringBuilder();
    		
    		for(int i = a.length() - 1; i >= 0; i --) {
    			char aChar = a.charAt(i);
    			char bChar = b.charAt(i + offset);
    			int aValue = Integer.parseInt(String.valueOf(aChar));
    			int bValue = Integer.parseInt(String.valueOf(bChar));
    			
    			aValue += carry;
    			int remain = getRemain(aValue, bValue, k);
    			int curCarry = getCarry(aValue, bValue, k);
    			
    			result.append(remain);
    			carry = curCarry;
    		}
    		
    		for(int i = offset - 1; i >= 0; i --) {
    			char bChar = b.charAt(i);
    			int bValue = Integer.parseInt(String.valueOf(bChar));
    			
    			bValue += carry;
    			int remain = getRemain(bValue, 0, k);
    			int curCarry = getCarry(bValue, 0, k);
    			
    			result.append(remain);
    			carry = curCarry;
    		}
    		
    		if(carry != 0) result.append(carry);
    		return result.reverse().toString();
    	}
    	
    	protected int getRemain(int a, int b, int k) {
    		int sum = a + b;
    		return sum % k;
    	}
    	
    	protected int getCarry(int a, int b, int k) {
    		int sum = a + b;
    		return sum >= k? 1:0;
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.