Reverse digits of a signed integer - Leet Code Solution
Problem Statement Given a signed integer, reverse digits of an integer. Return…
August 14, 2020
First try to understand question.
You can find the location of these two nodes on the tree. There can be three possibilities:
For Case-2, on finding that both nodes are on the same side. We will repeat our same algorithm going forward in that side only.
Lets see a code for this.
public class CommonAncestor {
public static class Node {
public int data;
public Node left;
public Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
/**
* To check whether a node exists in a root element
*/
private boolean covers(Node root, Node toSearch) {
if (root == null || toSearch == null) {
return false;
}
if (root.data == toSearch.data) {
return true;
}
return this.covers(root.left, toSearch) || this.covers(root.right, toSearch);
}
private Node helper1(Node root, Node node1, Node node2) {
if (root == null) {
return null;
}
if (root.data == node1.data || root.data == node2.data) {
return root;
}
boolean firstNodeFoundOnLeft = this.covers(root.left, node1);
boolean firstNodeFoundOnRight = this.covers(root.left, node2);
if (firstNodeFoundOnLeft != firstNodeFoundOnRight) {
//both are on different sides. Found result.
return root;
}
//both are on the same side.
return this.helper1(firstNodeFoundOnLeft ? root.left : root.right,
node1, node2);
}
public Node findCommonAncestor_1(Node root, Node node1, Node node2) {
if (!this.covers(root, node1) || !this.covers(root, node2)) {
//one or both nodes are not in the tree
System.out.println("Not covered");
return null;
}
return this.helper1(root, node1, node2);
}
}
helper1(root, node1, node2)
The function calls recursively, and same code repeats.
Consider the tree to be balanced tree.
covers()
is called twice. So, its 2 times O(n)
, which computes to O(n)
helper1()
function gets called on branches one time for each node.
2 * n/2 for both nodes.
Which comes out to be: 2n/2 + 2n/4 + 2n/8 ~= O(logn)
Total complexity of this code is O(n)
Problem Statement Given a signed integer, reverse digits of an integer. Return…
Sorting Problems Merge Sort Quick Sort Heap Sort Bubble Sort Selection Sort…
Big-O notation In simpler terms, its kind of a unit to measure how efficient an…
It is one of a simple algorithm to study for a beginner to understanding sorting…
Problem Statement Given an array, rotate the array to the right by k steps…
Its a tree based data structure which is a complete binary tree(all nodes have…
Introduction Strapi is a backend system provides basic crud operations with…
Introduction I had to create many repositories in an Github organization. I…
Introduction I was trying to download some youtube videos for my kids. As I have…
Introduction In this post, we will explore some useful command line options for…
Introduction In this post, we will see how we can apply a patch to Python and…
Introduction We will introduce a Package Manager for Windows: . In automations…