Category Archives: Logical Problems

String having unique characters


public class IsStringHavingUniqueChar {

	public static void main(String[] args) {
		System.out.println("isStringHavingUniqueCharacters: "+isStringHavingUniqueCharacters("Raaaahul"));
	}
	
	private static boolean isStringHavingUniqueCharacters(String str){
		
		boolean[] asciiArray = new boolean[256];
		for (int i = 0; i < str.length(); i++) {
			int charAscii = str.charAt(i);
			if(asciiArray[charAscii])
				return false;
			asciiArray[charAscii] = true;
		}
		
		return true;
	}
	
}

Binary Search

package com.multithreding.producerconsumer;
public class BinarySearch {
public static void main(String[] args) {
int[] array = {10,39,40,123};
int k = 39;
System.out.println(findElement(array, k));
}

public static int findElement(int[] array, int k){
int length = array.length;

int startIndex = 0;
int endIndex = length-1;
while (startIndex <= endIndex) {
int mid = (startIndex + endIndex)/2;
if(array[mid] == k){
return mid;
}

if(k < array[mid]){
endIndex = mid - 1;
}else{
startIndex = mid + 1;
}
}
return -1;
}
}

Frog Jump through leaves problem

Problem:

A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river.
You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in minutes.
The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X.
For example, you are given integer X = 5 and array A such that:
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
In minute 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.
Write a function:
class Solution { public int solution(int X, int[] A); }
that, given a non-empty zero-indexed array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.
If the frog is never able to jump to the other side of the river, the function should return −1.
For example, given X = 5 and array A such that:
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
the function should return 6, as explained above.
Assume that:
N and X are integers within the range [1..100,000];
each element of array A is an integer within the range [1..X].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(X), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

Solution of the problem:

private static int frogJump(int[] arrEl,int postion) {
		/** Marker array for the leaf found on the way. */
		boolean[] leafArray = new boolean[postion+1];
		
		/** Total step needed for frog. */
		int steps = postion;
		
		for(int i = 0; i<arrEl.length; i++) {
			
			/** if leaf needed for frog and it does not exist earlier. **/
			if(postion>=arrEl[i] && !leafArray[arrEl[i]]) {
				
				/* Mark leaf found */
				leafArray[arrEl[i]] = true;
				
				/** Reduce the step by one(coz one jump found). */
				steps--;
			}
			
			if(steps == 0 && arrEl[i]==postion) {
				return i;
			}
		}
		
		return -1;
	}

Passing car problem

Problem:

A non-empty zero-indexed array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.
Array A contains only 0s and/or 1s:
0 represents a car traveling east,
1 represents a car traveling west.
The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west. For example, consider array A such that: A[0] = 0 A[1] = 1 A[2] = 0 A[3] = 1 A[4] = 1 We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4). Write a function: class Solution { public int solution(int[] A); } that, given a non-empty zero-indexed array A of N integers, returns the number of pairs of passing cars. The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000. For example, given: A[0] = 0 A[1] = 1 A[2] = 0 A[3] = 1 A[4] = 1 the function should return 5, as explained above. Assume that: N is an integer within the range [1..100,000]; each element of array A is an integer that can have one of the following values: 0, 1. Complexity: expected worst-case time complexity is O(N); expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified.

Frog Problem: Count minimal number of jumps from position X to Y.

Problem:

A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D.
Count the minimal number of jumps that the small frog must perform to reach its target.
Write a function:

class Solution { public int solution(int X, int Y, int D); }

that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.
For example, given:
X = 10
Y = 85
D = 30
the function should return 3, because the frog will be positioned as follows:
after the first jump, at position 10 + 30 = 40
after the second jump, at position 10 + 30 + 30 = 70
after the third jump, at position 10 + 30 + 30 + 30 = 100
Assume that:
X, Y and D are integers within the range [1..1,000,000,000];
X ≤ Y.
Complexity:
expected worst-case time complexity is O(1);
expected worst-case space complexity is O(1).

Solution

        // Frog problem
	int frogMinimumCount(int X, int Y, int D) {
	    int numberOfJumps = 0;
	    
	    if((Y-X)<D){
	    	numberOfJumps = 1;
	    }
		if((Y-X)%D == 0){
			numberOfJumps = (Y-X)/D;
	    }else{
	    	numberOfJumps = ((Y-X)/D)+1;
	    }
		
		return numberOfJumps;
	}

Remove duplicate element of an integer array

Problem:
Remove duplicate element of an integer array.

Solution:

//Remove duplicate element of an integer array
	public void removeDuplicateElements(int[] A){
		// primitive  to Wrapper
		Integer[] integerArr = new Integer[A.length];
		for (int i = 0; i < integerArr.length; i++) {
			integerArr[i] = A[i];
		}
		
		Integer[] integerArr2 = new HashSet<Integer>(Arrays.asList(integerArr)).toArray(new Integer[0]);
		int[] outputArray = new int[integerArr2.length];
		for (int i = 0; i < outputArray.length; i++) {
			outputArray[i] = (int)integerArr2[i];
			System.out.println((int)outputArray[i]);
		}
	}

Find Mirror image of the string

Problem:
Find Mirror image of the string: like for name “arora”, “o” is the mirror image of arora.

Solution:

	//15. Find Mirror point of the String
	class mirrorImage {
	    public int solution(String S) {
	        int strLength = S.length();
	        if(strLength%2==0){
	         return -1;   
	        }
	        
	        int midPoint =  (strLength/2);
	        for(int i=0; i<midPoint; i++){
	            if(S.charAt((midPoint-1)-i)!=S.charAt(midPoint+1+i)){
	                return -1;
	            }
	        }
	        
	        return midPoint;
	    }
	}

Brackets Nested Problem

Problem:

A string S consisting of N characters is called properly nested if:

S is empty;
S has the form “(U)” where U is a properly nested string;
S has the form “VW” where V and W are properly nested strings.

For example, string “(()(())())” is properly nested but string “())” isn’t.

Write a function:

class Solution { public int solution(String S); }

that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.

For example, given S = “(()(())())”, the function should return 1 and given S = “())”, the function should return 0, as explained above.

Assume that:

N is an integer within the range [0..1,000,000];
string S consists only of the characters “(” and/or “)”.

Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

Solution:

public class ParenthesisMatching {
                public static void main(String[] args) {
                                Scanner scan = new Scanner(System.in);
                
                        /* Create Stack */
                                Stack<Character> stack = new Stack<Character>();
                                System.out.println("Parenthesis Matching Test\n");

                                /* Accepting expression */
                                System.out.println("Enter expression");
                                String exp = scan.next();

                                int len = exp.length();
                                for (int i = 0; i < len; i++) {
                                                char ch = exp.charAt(i);
                                                if (ch == '(') {
                                                                stack.push(ch);
                                                } else if (ch == ')') {
                                                                if(stack.peek() == '(') {
                                                                                stack.pop();
                                                                } else {
                                                                                break;
                                                                }
                                                }            
                                }
                                
                                if(stack.isEmpty() ) {
                                                System.out.println("Balanced parenthis !!");
                                } else {
                                                System.out.println("Not Balanced ");
                                }
                }
}

Brackets Problem(Determine whether a given string of parentheses is properly nested)

Problem:

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:
S is empty;
S has the form “(U)” or “[U]” or “{U}” where U is a properly nested string;
S has the form “VW” where V and W are properly nested strings.
For example, the string “{[()()]}” is properly nested but “([)()]” is not.
Write a function:
int solution(char *S);
that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.
For example, given S = “{[()()]}”, the function should return 1 and given S = “([)()]”, the function should return 0, as explained above.
Assume that:
N is an integer within the range [0..200,000];
string S consists only of the following characters: “(“, “{“, “[“, “]”, “}” and/or “)”.
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Solution of the Problem:

	private int characterSymmatry(String str){
		Stack<Character> stack = new Stack<Character>();
		
		for (int i = 0; i < str.length(); i++) {
			char characters = str.charAt(i);
			switch (characters) {
			case '{':
				stack.push(characters);
				break;
			case '[':
				stack.push(characters);
				break;

			case '(':
				stack.push(characters);
				break;

			case ')':
				if(!stack.isEmpty()){
					char c= stack.pop();
					if(c!='('){
						return 0;
					}
				}
				
				break;
			case ']':
				if(!stack.isEmpty()){
					char c2 = stack.pop();
					if(c2!='['){
						return 0;
					}
				}
				break;
			case '}':
				if(!stack.isEmpty()){
					char c3 = stack.pop();
					if(c3!='{'){
						return 0;
					}
				}
				break;
				
			default:
				break;
			}
		}
		
		if(stack.isEmpty()){
			return 1;
		}
		
		return 0;
	}