Monthly Archives: June 2021

Bitwise AND

by

Given an array of non-negative integers, count the number of unordered pairs of array
elements such that their bitwise AND is a power of 2.
For example, let’s say the array is arr = [10, 7, 2, 8, 3], and let ‘&’ denote the bitwise AND
operator. There are 6 unordered pairs of its elements that have a bitwise AND that is a
power of two:
For indices (0,1), 10 & 7 = 2, which is a power of 2.
For indices (0,2), 10 & 2 = 2, which is a power of 2.
For indices (0,3), 10 & 8 = 8, which is a power of 2.
For indices (0,4), 10 & 3 = 2, which is a power of 2.
For indices (1,2), 7 & 2 = 2, which is a power of 2.
For indices (2,4), 2 & 3 = 2, which is a power of 2.
Therefore, the answer is 6.

    public static long countPairs(List<Integer> arr) {
    // Write your code here
    int count = 0;
     for(int i = 0; i < arr.size(); i++){
         for(int j= i+1; j < arr.size(); j++){
             double a = Math.log(arr.get(i).intValue()&arr.get(j).intValue())/Math.log(2) ;
             if(a == (int) a)
             count++;
         }
     }
     return count;
    }

Counting Triangles

by
counting-trianglesDownload
	class Sides {
		int a;
		int b;
		int c;

		Sides(int a, int b, int c) {
			this.a = a;
			this.b = b;
			this.c = c;
		}

	}

	public int compare(Sides o1, Sides o2) {
		int[] o1Sides = new int[] { o1.a, o1.b, o1.c };
		Arrays.sort(o1Sides);
		int[] o2Sides = new int[] { o2.a, o2.b, o2.c };
		Arrays.sort(o2Sides);
		for (int i = 0; i < o1Sides.length; i++)
			if (o1Sides[i] != o2Sides[i])
				return -1;

		return 0;
	}

	public int countDistinctTriangles(ArrayList<Sides> arr) {
		if (arr.size() == 0)
			return 0;
		Collections.sort(arr, new Comparator<Sides>() {

			@Override
			public int compare(Sides o1, Sides o2) {
				int[] o1Sides = new int[] { o1.a, o1.b, o1.c };
				Arrays.sort(o1Sides);
				int[] o2Sides = new int[] { o2.a, o2.b, o2.c };
				Arrays.sort(o2Sides);
				for (int i = 0; i < o1Sides.length; i++)
					if (o1Sides[i] != o2Sides[i])
						return -1;

				return 0;
			}
		});
		int count = 1;
		for (int i = 1; i < arr.size(); i++) {
			if (compare(arr.get(i), arr.get(i - 1)) != 0)
				count++;
		}
		return count;
	}

Number of Visible Nodes

by
number-of-visible-nodesDownload
	  class Node {
		    int data; 
		    Node left; 
		    Node right; 
		    Node() {
		      this.data = 0; 
		      this.left = null; 
		      this.right = null; 
		    }
		    Node(int data) {
		      this.data = data; 
		      this.left = null; 
		      this.right = null; 
		    }
		  }
		  
	
	int visibleNodes(Node root) {
       Queue<Node> q = new LinkedList<Node>();
       Queue<Integer> level = new LinkedList<Integer>();
       q.add(root);
       level.add(1);
       int count = 0;
       while(!q.isEmpty()) {
    	   Node n = q.poll();
    	    count = level.poll();
    	   if(n.right != null ) {
    		   q.add(n.right);
    		   level.add(count+1);
    	   }
    	   if(n.left != null ) {
    		   q.add(n.left);
    		   level.add(count+1);
    	   }
       }
       return count;
	}

Minimum Length Substrings

by
minimum-length-substringsDownload
	public static int minLengthSubstring(String s, String t) {
		int min = Integer.MAX_VALUE;
		boolean found = false;
		for (int i = 0; i <= s.length(); i++) {
			for (int j = i; j <= s.length(); j++) {
				String takedString = s.substring(i, j);
				boolean contained = true;
				HashMap<Character, Integer> h = new HashMap<Character, Integer>();
				for (Character c : t.toCharArray()) {
					h.put(c, h.getOrDefault(c, 0) + 1);
				}
				for (Character c : takedString.toCharArray()) {
					h.put(c, h.getOrDefault(c, 0) - 1);
				}

				for (Character c : h.keySet()) {
					if (h.get(c) > 0)
						contained = false;
				}
				if (contained) {
					found = true;
					min = Integer.min(min, takedString.length());
				}
			}
		}
		if (!found)
			return -1;
		return min;
	}