Find a Number occurring odd number of times in a Given array

Objective: Given a array of integers, in which every elements occurs even number of times except one number which occurs add number of times. Find out that number. Example:   int[] A = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7 }; Element appearing add … Read more Find a Number occurring odd number of times in a Given array

Rearrange the Array of Given Range N, such that A[i]=i

AlgorithmsRearrange the Array of Given Range N, such that A[i]=i.

Objective: Given a array of length N, in which elements are in the range of 1 to N. All elements may not present in the array. If element is not present , there will be -1 present in the array. Rearrange the array such that A[i]=i and if i is not present, display -1 at that place. See example

Example:

Rearrange the Array of Given Range N, such that A[i]=i
Rearrange the Array of Given Range N, such that A[i]=i
Approach: – Time Complexity -O(N), Space Complexity – O(1)

Read moreRearrange the Array of Given Range N, such that A[i]=i

Find a Missing Number From a Sequence of Consecutive Numbers | XOR Method

Input:  Array, arrA[] with a miss­ing num­ber and Range

Out­put : miss­ing number

Example:

int A[] = { 1, 2, 7, 6, 3, 4 };
int range = 7;
Output: MIssing No is :5

In our earlier approach ” Click Here ” we have seen the method where we had calculated the Sum of numbers, but this approach might fail when number goes beyond the integer range.

XOR method will better solution in that case.

Approach: – Time Complexity -O(N), Space Complexity – O(1)

Read moreFind a Missing Number From a Sequence of Consecutive Numbers | XOR Method

Find the Max element in a Given Binary Tree

Objective: – Given a binary tree , Find the max element in it. Example: Approach: Use Recursion. Max will the Max(root, max element in the left subtree, max element in right subtree) Recursively solve for the max element in the left subtree and right subtree. Complete Code:Run This Code Output: Max element in Binary Tree: 35

Find the Deepest Node in a Binary Tree.

Objective: – Given a binary tree, write an algorithm to Find the deepest node in it.

Approach:

  • Take two global variable as “deepestlevel” and “value“.
  • starting with level=0, Do the inorder traversal and whenever you go down one level ( root.left OR root.right), increase the level by 1.
  • Keep checking if deepestlevel < level, if yes then update the “deepestlevel ” and “value “.
  • At the end return “value“, which will the deepest node value.
  • See the code for better explanation.

Read moreFind the Deepest Node in a Binary Tree.

Find numbers which are palindrome in both their decimal and octal Representations

Objective: Given a range of integers, find all the numbers which are palindrome when they are represented in Decimal Value( base 10) and in Octal value(base 8).

Example :

Number : 373 (Decimal) and digits are palindrome.

Convert it into Octal which is 565 and that's also palindrome.

Approach:

Read moreFind numbers which are palindrome in both their decimal and octal Representations

Find Increasing Triplet Sub-sequence

Objective: Given an integer array A[1..n], find an instance of i,j,k where 0 < i < j < k <= n and A[i] < A[j] < A[k].

Example :

int arrA[] = { 10, 9, 4, 3, 2, 1, 7, 3, 1, 11, 2, 6, 9 };
Output :
Increasing triplets are

1, 7, 11
1, 2, 6
1, 3, 9

likewise you can find more triplets.

Approach:

Read moreFind Increasing Triplet Sub-sequence

Convert Decimal into Irreducible Fraction

Objective: Given a decimal number, convert it into irreducible fraction. Irreducible Fraction : An irreducible fraction is a fraction in which the numerator and denominator are integers that have no other common divisors than 1. Ex: 1/4, 5/20, 1/2 etc Example: Input: 0.35 Output : 7/20 Input: 1.2 Output : 6/5 Approach: Split using decimal … Read more Convert Decimal into Irreducible Fraction

Generate All Strings of n bits.

Objec­tive: Generate All Strings of n bits, consider A[0..n-1] is an array of size n.

Example :

n = 3
Output:
[0, 0, 0]    [1, 0, 0]    [0, 1, 0]    [1, 1, 0]

[0, 0, 1]     [1, 0, 1]     [0, 1, 1]    [1, 1, 1]

Read moreGenerate All Strings of n bits.

Find The Missing Duplicate in a Given Array.

Bit Manipulation

Objec­tive: Given an Integer array. Array contains duplicates of all the numbers in array except one number . Find that number.

Example :

int [] A = { 2,1,3,5,5,3,2,1,6,7,7,8,8};
Output : Missing duplicate is 6

Read moreFind The Missing Duplicate in a Given Array.

Delete X Nodes After Y Nodes In a Linked List

Objective: Given a Linked List and x and y. Delete x number of nodes after y nodes from the start. Example: ->10->20->30->40->50->60->70->80->90->100->110->120 Deleted 4 Nodes after 5 Nodes ->10->20->30->40->50->100->110->120 Approach: We need two pointers. One pointer at one node prior to the nodes to be deleted. ( Move it by y starting from the head). … Read more Delete X Nodes After Y Nodes In a Linked List

Check if Array Contains All Elements Of Some Given Range

Objective: Given an array of unsorted numbers, check if it contains all elements of some given range.

Examples:

int[] arrA = { 11, 17, 13, 19, 15, 16, 12, 14 };
Range : 12-15
Output: True

Approach:

Naive Approach: Sorting . Time Complexity – O(nlogn).

Better Approach: Time Complexity – O(n).

Read moreCheck if Array Contains All Elements Of Some Given Range

Check if Array is Consecutive Integers

Objective: Given a array of unsorted numbers, check if all the numbers in the array are consecutive numbers.

Examples:

int [] arrA = {21,24,22,26,23,25}; - True
(All the integers are consecutive from 21 to 26)
int [] arrB = {11,10,12,14,13}; - True
(All the integers are consecutive from 10 to 14)
int [] arrC = {11,10,14,13}; - False
(Integers are not consecutive, 12 is missing)

Approach:

Naive Approach: Sorting . Time Complexity – O(nlogn).

Better Approach: Time Complexity – O(n).

Read moreCheck if Array is Consecutive Integers

Find the subarray with sum to a Given Value.

Objective: Given an array (non-negative) and an integer, Find the Subarray whose sum is equal to the given integer.

Examples:

int[] arrA = { 25, 12, 14, 22, 19, 15, 10, 23 };
Integer = 55
Output : 55 is found between indexes 2 and 4
And Elements are : 14 22 19

Approach :

Naive Approach: Use 2 loops . Time Complexity – O(n2).

Better Approach: Time Complexity – O(n)

Read moreFind the subarray with sum to a Given Value.

Find intersection between Two Sorted Arrays.

Objective: Given two sorted arrays, Find intersection point between them.

Examples:

int[] a = { 1, 2, 3, 6, 8, 10 };
int[] b = { 4, 5, 6, 11, 15, 20 };
Output: Intersection point is : 6

Approach:

Naive Approach: Use 2 loops and compare each elements in both array and as soon as you find the intersection point, return it. Time Complexity – O(n2).

Better Approach: Time Complexity – O(n)

  • Say Arrays are arrA[] and arrB[] and indexes for navigation are x and y respectively.
  • Since arrays are sorted, compare the first element of both the arrays.(x=0, y=0)
  • If both elements are same, we have our intersection point, return it.
  • Else if element of arrA[x] > element of arrB[y], increase the arrB[] index, y++.
  • Else if element of arrA[x] < element of arrB[y], increase the arrA[] index, x++.
  • If any of the array gets over that means you have not found the intersection point. return -1.

Read moreFind intersection between Two Sorted Arrays.