Find two elements in the array add up to given number

Example:
Input : {1,2,4,5,3},  number = 8
Output : 5, 3 (because 5+3 = 8(given number))

Implementation

Method 1:

public static void findSum3(int []a, int sum){
        if(array == null || array.length == 0)
               return ;

for(int i = 0; i < a.length; i++){
for(int j = i+1; j < a.length; j++){
if(a[i] + a[j] == sum){
System.out.println(a[i] + " "+a[j]);
break;
}
}
}
}

Time Complexity : O(N^2)
Space Complexity : O(1)

Method 2:
public static void findSum(int []a, int sum){
        if(array == null || array.length == 0)
               return ;
 
        Hashtable h = new Hashtable();

for(int i = 0; i < a.length; i++){
               //if sum-a[i] is in hashtable then we already found the pair.
if(h.containsKey(sum - a[i])){       
System.out.println(a[i] +" "+(sum - a[i]));
}
else{   //put the element of array into hashtable, if it doesnot have it.
h.put(a[i], true);             
}
}
}

Time Complexity : O(N)
Space Complexity : O(N)

Method 3:

public static void findSum2(int []a, int sum){
     if(array == null || array.length == 0)
               return ;

//sort the array
Arrays.sort(a);

int first = 0;
int last = a.length - 1;       //last element
 
     while(first < last){
int s = a[first] + a[last]; //sum of first and last element of array
if(s == sum){
System.out.println(a[first] +" "+ a[last]);
first++;
last--;
}else{
if(s < sum)
first++;
else
last--;
}
}
}

Time Complexity : O(NlogN)
Space Complexity: O(1)

Find the maximum repeating number in the array

Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k <= n. Find the maximum repeating number in this array. For example, let k be 8 the given array be arr[] = {2, 3, 3, 5, 3, 4, 1, 7};  the maximum repeating number would be 3.

Implementation

Method 1:

static int findMaxRepeatingNumber(int []array, int k){
     //Boundary condition
if(array == null || array.length == 0)
return -1;

int maxCount = Integer.MIN_VALUE;  //max count
int number = -1;
     //Iterate over all the elements of the array
for(int i = 0; i < array.length; i++){
int count = 1; //count of current number
for(int j = 1; j < array.length; j++){
if(array[i] == array[j])
count++;
}
if(count > maxCount){
maxCount = count;
number = array[i];
}
}
return number;  //return the maximum repeating number
}

Time Complexity : O(N^2)
Space Complexity : O(1)

Method 2:

static int findMaxRepeatingNumber2(int []array, int k){
      //Boundary condition
if(array == null || array.length == 0)
return -1;

int []count = new int[k]; //hold the count of number
 
      for(int i = 0; i < array.length; i++){
count[ array[i] ] ++;
}

//get the max count
int max = Integer.MIN_VALUE;
int number = -1;
 
      for(int i = 0; i < k; i++){
if(max < count[i]){
max = count[i];
number = i;
}
}
return number;
}

Time Complexity : O(N)
Space Complexity : O(K)

Given a float number, convert it into the string WITHOUT using any inbuilt function/library.

Implementation

class BinaryRepreOfRealNumberEx{
//function to convert integer into binary format
//Example : Input 2
//         Output : 10
public static String convertIntegerIntoBinaryFormat(int n){
StringBuffer binary = new StringBuffer();
while(n > 0){
binary.append( n & 1);
n = n >> 1;
}
binary.reverse();
return new String(binary);
}

//function to convert double into binary format
public static String convertDoubleIntoBinaryFormat(double n){
if(n >= 1 || n <= 0 )
return "error";

StringBuilder result = new StringBuilder();
result.append(".");

while(n > 0){
double r = n*2;
if(r >= 1){
result.append(1);
n = r - 1;
}else{
result.append(0);
n = r;
}
}
return result.toString();
}

//function to convert number into binary format
public static String convertIntoBinaryFormat(double number){
int t = (int)number;
String intPart = binary(t);

double d = number - t;
String doublePart = printBinary(d);

return intPart + doublePart;
}

public static void main(String []args){
String result = "";
double n = 2.2;

result = convertIntoBinaryFormat(n);
System.out.println("Binary Representation of "+ n +" "+result );
}
}

Reverse a linked list

Reverse a linked list
Example :
Input : 1->2->3
Output 3->2->1

Implementation

class ReverseLinkedListEx{
//Tree
static class Node{
int data;
Node next = null;

public Node(int data){
this.data = data;
}

               //Utility to create a list
public void insert(int data){
Node newNode = new Node(data);

Node n = this;
if(n == null)
n = newNode;

while(n.next != null){
n = n.next;
}
n.next = newNode;
}

                //function to reverse the given list
public Node reverse(Node head){
Node previous = null;
Node current = head;
Node forward;

while(current !=null){
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
return previous;
}

public void display(){
Node head = this;

if(head == null)
return;

while(head != null){
System.out.println(head.data);
head = head.next;
}
}
}

public static void main(String[] args){
Node root = new Node(1);
root.insert(2);
root.insert(3);

System.out.println("Reversed list :");
                  Node rev = root.reverse(root);
rev.display();
}
       }

Output: 3->2->1

Time Complexity : O(N)
Space Complexity : O(1)

Add two numbers represented as linkedlist

Add two numbers represented as linkedlist.

Example
Input : list1: 7->1->6   (617)
          list2: 5->9->2    (295)
 Output: 2->1->9   (915)

Implementation

class AddLinkedListNumber{
//LinkedList
static class Node{
int data;
Node next = null;

public Node(int data){
this.data = data;
}

//Utility to add new linkedlist node at the end of existing list
public void insertAtEnd(int data){
Node newNode = new Node(data);
Node n = this;

while(n.next != null){
n = n.next;
}
n.next = newNode;
}

//method to add 2 lists
public static Node addLists(Node n1 , Node n2 , int carry){
//Boundary Condition
if(n1 == null && n2 == null && carry == 0)
return null;

Node result = new Node(carry);
int value = carry;
 
                        if(n1 != null)
value += n1.data;

if(n2 !=null)
value += n2.data;

result.data = value%10; //second digit of number

//recurse
if(n1 != null || n2 !=null || value >= 10){
Node more = addLists(n1 == null ? null:n1.next,
n2 == null ? null:n2.next,
value >=10 ? 1 : 0);

result.next = more;
}
return result;
}

//Utility to display linkedlist
public void display(){
Node head = this;

while(head != null){
if(head.next !=null)
System.out.print(head.data+"->");
else
System.out.print(head.data);
head = head.next;
}
}
}

public static void main(String []args){
Node list = new Node(7);;
Node list2 =  new Node(5);

list.insertAtEnd(1);
list.insertAtEnd(6);

list2.insertAtEnd(9);
list2.insertAtEnd(2);

  Node result = Node.addLists(n1,n2,0);
result.display();
}
 }

Output:
2->1->9

Multiply two number represented as Linked List and return the result as Linked list

Ex :
Input : list = 9->9->9
          list2 = 1->2->3

Output : 1228->7->7

class MultiplyLinkedListNumber{
//Tree
static class Node{
int data;
Node next = null;

public Node(int data){
this.data = data;
}

//Utility to insert new node at the end of given list
public void insertAtEnd(int data){
Node newNode = new Node(data);
Node n = this;
while(n.next != null){
n = n.next;
}
n.next = newNode;
}

//Utility function to print the given list
public void display(){
Node head = this;

while(head != null){
if(head.next !=null)
System.out.print(head.data+"->");
else
System.out.print(head.data);
head = head.next;
}
}
}

//Function to multiply two given lists 
//return resulted list
static Node multiply(Node head, Node head1){
//Base Condition
if(head == null || head1 == null)
return null;

int number = getNumber(head);  //convert one list into number

//traverse the second list and multiply the number with the current element of the list and store in the new list.
Node current = head1; Node result = null;
while(current != null){
if(result == null){
result = new Node(current.data * number);
}else{
                               //multiply current element with the "number" and store in the new list node
Node temp = new Node(current.data * number);  
temp.next = result;
result = temp;
}
current = current.next;  
}
return process(result);
}

//Utility function
static Node process(Node list){
Node head = list;
int carry = 0, i = 0;
//traverse the given list
while(head != null && head.next != null){
i = head.data;
head.data = (carry + i)%10;
carry = (i+carry)/10;
head = head.next;
}
head.data = head.data + carry;
return reverse(list);
}

//Utility function to reverse the given list
//Ex: Input : 1->2->3
//Output : 3->2->1
static Node reverse(Node list){
if(list == null)
return null;

Node current = list, previous = null, forward;
while(current != null){
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
return previous;
}

//Utility function to convert list into number
//Ex : Input = 1->2->3
//Output = 123
static int getNumber(Node head){
int number = 0;
while(head != null){
number = 10*number + head.data;
head = head.next;
}
return number;
}

public static void main(String... args){
//create the first list
Node list = new Node(9);
list.insertAtEnd(9);
list.insertAtEnd(9);

//create the second list
Node list1 = new Node(1);
list1.insertAtEnd(2);
list1.insertAtEnd(3);

//call the multiply method
Node result = multiply(list, list1);
 
//print the list
result.display();
}
   }

Output : 1228->7->7

Time Complexity : O(N)
Space Complexity : O(1)

Find the kth largest element in a Binary Search Tree

Find the kth largest element in a Binary Search Tree.

Let us consider the below binary search tree:

if k = 2, then 2nd largest element is 6
if k = 4, then 4th largest element is 4

Solution: We traverse the tree in descending order and keep a count of number of nodes visited. When this count is equal to 'k', print the element.

Implementation:

class KthLargestElementInBST{
static class Tree{
int data;
Tree left = null;
Tree right = null;

public Tree(int data){
this.data = data;
}

//Utility function to create minimal bst
public static Tree createBST(int []a, int left, int right){
if(right < left)
return null;

int mid = (left + right)/2;
Tree root = new Tree(a[mid]);
root.left = createBST(a, left, mid - 1);
root.right = createBST(a, mid + 1, right);

return root;
}

//method to get the kth largest value in BST
static int index = 0; //Counter variable
public static void getElement(Tree root, int k){
                      //Base condition
if(root == null)
return;

getElement(root.right, k);   //first traverse the right sub tree
if(++index == k){
                              System.out.println(root.data);
return;
                      }
getElement(root.left, k);    //then traverse the left sub tree
}
}

public static void main(String... args){
int []a = {1,2,3,4,5,6,7};
Tree root = Tree.createBST(a, 0, a.length - 1);
           Tree.getElement(root, 2);
}
 }

Output: 6