Most typical Programs
/*
Sum of all odd frequency elements in an array
Given an array of integers containing duplicate elements. The
task is to find the sum of all odd occurring elements in the given
array. That is the sum of all such elements whose frequency
is odd in the array.
Examples:
Input : arr[] = {1, 1, 2, 2, 3, 3, 3}
Output : 9
The odd occurring element is 3, and it's number
of occurrence is 3. Therefore sum of all 3's in the
array = 9.
Input : arr[] = {10, 20, 30, 40, 40}
Output : 60
Elements with odd frequency are 10, 20 and 30.
Sum = 60.
*/
int SumOfOddOccuringElements(int arr[], int size)
{
map<int,
int>Map;
map<int,
int>::iterator itr;
for (int i = 0;i<size;i++)
{
Map[arr[i]]++;
}
int sum =
0;
for (itr =
Map.begin(); itr!= Map.end(); ++itr)
{
if
((itr->second)%2 == 1)
{
sum = sum +
(itr->second)*(itr->first);
}
}
return
(sum);
}
/*
Calculate the angle between hour hand and minute hand
This problem is know as Clock angle problem where we need to
find angle between hands of an analog clock at a given time.
Examples:
Input: h = 12:00, m =
30.00
Output: 165 degree
Input: h = 3.00, m =
30.00
Output: 75 degree
The idea is to take 12:00 (h = 12, m = 0) as a reference.
Following are detailed steps.
1) Calculate the angle made by hour hand with respect to
12:00 in h hours and m minutes.
2) Calculate the angle made by minute hand with respect to
12:00 in h hours and m minutes.
3) The difference between two angles is the angle between two
hands.
How to calculate the two angles with respect to 12:00?
The minute hand moves 360 degree in 60 minute(or 6 degree in
one minute) and hour hand moves 360 degree in
12 hours(or 0.5 degree in 1 minute). In h hours and m
minutes, the minute hand would move (h*60 + m)*6 and hour hand
would move (h*60 + m)*0.5.
*/
void calAngle(int
h, int m)
{
if (h <0
|| m < 0 || h >12 || m > 60)
printf("Wrong
input");
if (h ==
12)
{
h = 0;
}
if (m ==
60)
{
m = 0;
}
int
hourAngle = 0.5*(60*h + m);
int
minuteAngle = 6*m;
int angle
= abs(hourAngle - minuteAngle);
angle = min(360-angle, angle);
cout<<angle<<endl;
}
/*
Printing Longest Common Subsequence
Given two sequences, print the longest subsequence present in
both of them.
Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of
length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of
length 4.
We have discussed Longest Common Subsequence (LCS) problem in
a previous post. The function discussed there was mainly to find the length of LCS.
To find length of LCS, a 2D table L[][] was constructed. In this post, the
function to construct and print LCS is discussed.
Following is detailed algorithm to print the LCS. It uses the
same 2D table L[][].
1) Construct L[m+1][n+1] using the steps discussed in
previous post.
2) The value L[m][n] contains length of LCS. Create a
character array lcs[] of length equal to the length of lcs plus 1 (one extra to
store \0).
2) Traverse the 2D array starting from L[m][n]. Do following
for every cell L[i][j]
…..a) If characters (in X and Y) corresponding to L[i][j] are
same (Or X[i-1] == Y[j-1]), then include this character as part of LCS.
…..b) Else compare values of L[i-1][j] and L[i][j-1] and go
in direction of greater value.
*/
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
#include<iostream>
#include<cstring>
#include<cstdlib>
void lcs( char
*X, char *Y, const
int m, const int n )
{
int
L[10][10];
/* Following steps
build L[m+1][n+1] in bottom up fashion. Note
that L[i][j]
contains length of LCS of X[0..i-1] and Y[0..j-1] */
for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
if (i ==
0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
// Following code
is used to print LCS
int index =
L[m][n];
// Create a
character array to store the lcs string
char
lcs[10];
if (index!=
0)
lcs[index] = '\0'; // Set the terminating
character
// Start from the
right-most-bottom-most corner and
// one by one
store characters in lcs[]
int i = m, j
= n;
while (i
> 0 && j > 0)
{
// If current
character in X[] and Y are same, then
// current
character is part of LCS
if
(X[i-1] == Y[j-1])
{
lcs[index-1] = X[i-1]; // Put current character in result
i--; j--; index--; // reduce values
of i, j and index
}
// If not same,
then find the larger of two and
// go in the
direction of larger value
else if (L[i-1][j]
> L[i][j-1])
i--;
else
j--;
}
// Print the lcs
cout << "LCS
of " << X << " and
" << Y << " is "
<< lcs<<endl<<endl;
}
/*
convert a number m to n with minimum operations. The operations
allowed were -1 and *2.
For Eg : 4 and 6. Answer is 2.
1st operation : -1 -> 4-1 = 3.
2nd operation : * -> 3 * 2 =6.
*/
int converNumber(int m, int n)
{
if (m ==
0|| n == 0)
{
return
0;
}
if
(m>n)
{
return
(m-n);
}
if (m
<= 0 && n>0)
{
return
(-1);
}
if (n %2
== 1)
{
return
1 + converNumber(m -1, n);
}
else
{
return
1 + converNumber(m, n%2);
}
}
/*
Remove duplicates from unsorted array
Given an unsorted array of integers, Print the array after
removing the duplicate elements from it.
We need to print distinct array elements according to their
first occurrence.
Examples:
Input : arr[] = { 1, 2, 5, 1, 7, 2, 4, 2}
Output : 1 2 5 7 4
Explanation : {1, 2} appear more than one time.
Approach :
Take a hash map, in which will store all the elements which
has appeared before.
Traverse the array.
Check if the element is present in the hash map.
If yes, continue traversing the array.
Else Print the element.
*/
#include<map>
void removeDuplicates(int arr[], int size)
{
map<int,
int>Map;
for (int i = 0;i<size;i++)
{
Map[arr[i]] = Map[arr[i]] + 1;
}
int count
= 0;
map<int,
int>::iterator itr;
for (itr =
Map.begin();itr!= Map.end(); ++itr)
{
cout<<itr->first<<"---------->"<<itr->second<<endl;
if
(itr->second >1)
{
count++;
}
}
cout<<"Number
of duplicates elements = "<<count<<endl;
}
/*
Next Greater Element
Given an array, print the Next Greater Element (NGE) for
every element. The Next greater Element for an element x is the first
greater element on the right side of x in array. Elements for
which no greater element exist, consider next greater element as -1.
Examples:
a) For any array, rightmost element always has next greater
element as -1.
b) For an array which is sorted in decreasing order, all
elements have next greater element as -1.
c) For the input array [4, 5, 2, 25}, the next greater elements
for each element are as follows.
Element NGE
4 -->
5
5 -->
25
2 -->
25
25 -->
-1
*/
void printNextGreaterElement(int arr[], int size)
{
stack<int>st;
st.push(arr[0]);
for (int i = 1;i<size;i++)
{
if
(st.empty())
{
st.push(arr[i]);
continue;
}
while(!st.empty()&&(arr[i]>=st.top()))
{
cout<<st.top()<<"------------------>"<<arr[i]<<endl;
st.pop();
}
st.push(arr[i]);
}
while(!st.empty())
{
cout<<st.top()<<"------------------>"<<"-1"<<endl;
st.pop();
}
}
/*
Remove duplicates from a string in O(1) extra space
Given a string str of lowercase characters, the task is to
remove duplicates and return a resultant string without modifying
the order of characters in the original string.
Examples:
Input: str = "geeksforgeeks"
Output: geksfor
Input: str = "characters"
Output: chartes
*/
string
removeDuplicates(string str)
{
int
counter = 0;
int x = 1;
int j = 0;
int len =
0;
for(int i =0;i<str.length();i++)
{
x = str[i] - 97;
if
(0 == (counter&(1<<x)))
{
counter = counter |
(1<<x);
str[len] = x + 'a';
len++;
}
}
string str1 = str.substr(0, len);
return
str1;
}
Next Smaller Element
Given
an array, print the Next Smaller Element (NSE) for every element. The Smaller
smaller Element for an element x is the first smaller element on the right side
of x in array. Elements for which no smaller element exist (on right side),
consider next smaller element as -1.
Examples:
a) For any array, rightmost element always has next smaller element as -1.
b) For an array which is sorted in increasing order, all elements have next smaller element as -1.
c) For the input array [4, 8, 5, 2, 25}, the next smaller elements for each element are as follows.
a) For any array, rightmost element always has next smaller element as -1.
b) For an array which is sorted in increasing order, all elements have next smaller element as -1.
c) For the input array [4, 8, 5, 2, 25}, the next smaller elements for each element are as follows.
Element NSE
4 --> 2
8 --> 5
5 --> 2
2 --> -1
25 --> -1
d) For the input array [13, 7, 6, 12}, the
next smaller elements for each element are as follows.
Element NSE
13 --> 7
7 --> 6
6 --> -1
12 --> -1
|
// A Stack based C++ program to
find next
// smaller element for all array
elements.
#include <bits/stdc++.h>
using namespace std;
void nextSmallerElement(int arr[], int
size)
{
stack<int>st;
st.push(arr[0]);
for(int i
=1;i<size;i++)
{
while(!st.empty()&&st.top()>arr[i])
{
cout<<st.top()<<"-------->"<<arr[i]<<endl;
st.pop();
}
st.push(arr[i]);
}
while (!st.empty())
{
cout<<st.top()<<"-------->"<<"-1"<<endl;
st.pop();
}
}
/* prints element and NSE pair for
all
elements of arr[] of size n */
void printNSE(int arr[], int n)
{
stack<int>
s;
/* push
the first element to stack */
s.push(arr[0]);
// iterate
for rest of the elements
for (int i = 1; i
< n; i++) {
if (s.empty()) {
s.push(arr[i]);
continue;
}
/*
if stack is not empty, then
pop
an element from stack.
If
the popped element is smaller
than
next, then
a) print
the pair
b) keep
popping while elements are
smaller
and stack is not empty */
while (s.empty() == false && s.top() > arr[i]) {
cout
<< s.top() << " --> " << arr[i] << endl;
s.pop();
}
/*
push next to stack so that we can find
next
smaller for it */
s.push(arr[i]);
}
/* After
iterating over the loop, the remaining
elements in stack do
not have the next smaller
element, so print -1
for them */
while (s.empty() == false) {
cout
<< s.top() << " --> " << -1 << endl;
s.pop();
}
}
/* Driver program to test above
functions */
int main()
{
int arr[] = { 11, 13, 21, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
printNSE(arr,
n);
return 0;
}
|
Output:
21
--> 3
13
--> 3
11
--> 3
3
--> -1
Time Complexity: O(n).
The worst case occurs when all elements are sorted in increasing order. If
elements are sorted in increasing order, then every element is processed at
most 4 times.
a) Initially pushed to the stack.
b) Popped from the stack when next element is being processed.
c) Pushed back to the stack because next element is smaller.
d) Popped from the stack in step 3 of algo.
a) Initially pushed to the stack.
b) Popped from the stack when next element is being processed.
c) Pushed back to the stack because next element is smaller.
d) Popped from the stack in step 3 of algo.
Given a sorted array and a number x, find the pair in array
whose sum is closest to x
Given
a sorted array and a number x, find a pair in array whose sum is closest to x.
Examples:
Input: arr[] = {10, 22, 28, 29, 30, 40}, x = 54
Output: 22 and 30
Input: arr[] = {1, 3, 4, 7, 10}, x = 15
Output: 4 and 10
void closestPair(int arr[], int
size, int sum)
{
int j = size - 1;
int
m = 0;
int
l = 0;
int
i =0;
while(i<j)
{
if
(arr[i] + arr[j] <= sum)
{
m
= i;
l
= j;
i++;
j--;
}
else
if (arr[i] + arr[j] > sum)
{
j--;
}
else
{
i++;
}
}
cout<<"("<<m<<","<<l<<")";
}
// Simple C++ program to find the
pair with sum closest to a given no.
#include <iostream>
#include <climits>
#include <cstdlib>
using namespace std;
// Prints the pair with sum closest
to x
void printClosest(int arr[], int n,
int x)
{
int res_l, res_r; // To store indexes of result pair
//
Initialize left and right indexes and difference between
// pair sum
and x
int l = 0, r = n-1, diff = INT_MAX;
// While
there are elements between l and r
while (r > l)
{
//
Check if this pair is closer than the closest pair so far
if (abs(arr[l] + arr[r] - x) < diff)
{
res_l
= l;
res_r
= r;
diff
= abs(arr[l] + arr[r] - x);
}
//
If this pair has more sum, move to smaller values.
if (arr[l] + arr[r] > x)
r--;
else // Move to larger values
l++;
}
cout
<<" The closest pair is " << arr[res_l] << " and " << arr[res_r];
}
// Driver program to test above
functions
int main()
{
int arr[] = {10, 22, 28, 29, 30, 40}, x = 54;
int n = sizeof(arr)/sizeof(arr[0]);
printClosest(arr,
n, x);
return 0;
}
Longest subarray having maximum sum
Given an array arr[] containing n integers. The
problem is to find the length of the subarray having maximum sum. If there
exists two or more subarrays with maximum sum then print the length of the
longest subarray.
Examples:
Input : arr[] = {5, -2, -1, 3, -4}
Output : 4
There are two subarrays with maximum sum:
First is {5}
Second is {5, -2, -1, 3}
Therefore longest one is of length 4.
Input : arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}
Output : 5
The subarray is {4, -1, -2, 1, 5}
|
// C++ implementation to find the
length of the longest
// subarray having maximum sum
#include <bits/stdc++.h>
using namespace std;
// function to find the maximum
sum that
// exists in a subarray
int maxSubArraySum(int arr[], int size)
{
int max_so_far = arr[0];
int curr_max = arr[0];
for (int i = 1; i
< size; i++) {
curr_max
= max(arr[i], curr_max + arr[i]);
max_so_far
= max(max_so_far, curr_max);
}
return max_so_far;
}
// function to find the length of
longest
// subarray having sum k
int lenOfLongSubarrWithGivenSum(int arr[], int n, int k)
{
//
unordered_map 'um' implemented
// as hash
table
unordered_map<int,
int> um;
int sum = 0, maxLen = 0;
//
traverse the given array
for (int i = 0; i
< n; i++) {
//
accumulate sum
sum
+= arr[i];
//
when subarray starts from index '0'
if (sum == k)
maxLen
= i + 1;
//
make an entry for 'sum' if it is
//
not present in 'um'
if (um.find(sum) == um.end())
um[sum]
= i;
//
check if 'sum-k' is present in 'um'
//
or not
if (um.find(sum - k) != um.end()) {
//
update maxLength
if (maxLen < (i - um[sum - k]))
maxLen
= i - um[sum - k];
}
}
//
required maximum length
return maxLen;
}
// function to find the length of
the longest
// subarray having maximum sum
int lenLongSubarrWithMaxSum(int arr[], int n)
{
int maxSum = maxSubArraySum(arr, n);
return lenOfLongSubarrWithGivenSum(arr, n, maxSum);
}
// Driver program to test above
int main()
{
int arr[] = { 5, -2, -1, 3, -4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout
<< "Length of longest subarray having maximum sum = "
<<
lenLongSubarrWithMaxSum(arr, n);
return 0;
}
Power Set
Power Set Power set P(S) of a set S is
the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a},
{b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.
If
S has n elements in it then P(s) will have 2^n elements
Set = [a,b,c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111
Value of Counter Subset
000 -> Empty set
001 -> a
010 -> b
011 -> ab
100 -> c
101 -> ac
110 -> bc
111 -> abc
Output :
a
b
ab
c
ac
bc
abc
Time
Complexity: O(n2^n)
|
Output:
Length
of longest subarray having maximum sum = 4
Time Complexity: O(n).
Auxiliary Space: O(n).
Auxiliary Space: O(n).
Hard Programs:-
[01] https://www.geeksforgeeks.org/find-maximum-in-a-stack-in-o1-time-and-o1-extra-space/
[02] https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/
[03] https://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/
[04] https://www.geeksforgeeks.org/maximum-product-subarray/
[05] https://www.geeksforgeeks.org/maximum-product-subarray/
[06] https://www.geeksforgeeks.org/longest-subarray-having-maximum-sum/
[07] https://www.geeksforgeeks.org/next-smaller-element/
[08] https://www.geeksforgeeks.org/check-if-an-array-is-sorted-and-rotated-clockwise/
[09] https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
[10] https://www.geeksforgeeks.org/longest-sub-array-sum-k/
[11] https://www.geeksforgeeks.org/given-sorted-array-number-x-find-pair-array-whose-sum-closest-x/
[12] https://www.geeksforgeeks.org/remove-duplicates-from-a-string-in-o1-extra-space/
[13] https://www.geeksforgeeks.org/find-the-two-repeating-elements-in-a-given-array/
[14] https://www.geeksforgeeks.org/find-sum-non-repeating-distinct-elements-array/
[15] https://www.geeksforgeeks.org/find-the-nearest-smaller-numbers-on-left-side-in-an-array/
[16] https://www.youtube.com/watch?v=uFso48YRRao (Next Greater Element)
https://www.geeksforgeeks.org/next-greater-element/
[17] Next Smaller Element (Try it yourself solving it)
[18] https://www.geeksforgeeks.org/check-if-the-characters-in-a-string-form-a-palindrome-in-o1-extra-space/
[19]
Easy Programs:-
[1] https://www.geeksforgeeks.org/check-whether-two-strings-are-anagram-of-each-other/
Dynamic Programs
[1] https://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/
Not Solved Problems:-
[1] https://www.geeksforgeeks.org/shuffle-2n-integers-format-a1-b1-a2-b2-a3-b3-bn-without-using-extra-space/
[2] https://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/
streams Programs:-
[1] https://www.geeksforgeeks.org/select-a-random-number-from-stream-with-o1-space/
Stack/Queue Programs:-
[1] https://www.geeksforgeeks.org/queue-using-stacks/
[2] https://www.geeksforgeeks.org/implement-stack-using-queue/
[3] https://www.youtube.com/watch?v=uFso48YRRao (Next Greater Element)
Most Typical Problems:-
[1] https://www.geeksforgeeks.org/minimum-number-of-swaps-required-to-sort-an-array-set-2/
[2] https://www.geeksforgeeks.org/find-the-smallest-window-in-a-string-containing-all-characters-of-another-string/ [Not able to understand its solution]
Comments
Post a Comment