swapnilkant11
BAN USEROne of the best approaches is to use the max heap, we can insert all the elements of the array or the large size block and then we can pop out the first k elements to get the kth largest element in the largest size block
Implementation:
#include<bits/stdc++.h>
using namespace std;
int findrepeatedelement(int arr[], int n, int k){
priority_queue<int> p;
for(int i = 0; i < n; i++)
p.push(arr[i]);
while(--k)
p.pop();
return p.top();
}
int main(){
int arr[] = {10, 5, 1, 30, 20};
cout<<findrepeatedelement(arr, 5, 3);
return 0;
}
can we also do it with the max heap I guess?
- swapnilkant11 June 07, 2019One of the best approaches to solving the above algorithm is with the help of a heap, you will have to implement a max heap using a priority queue.
Implementation:
#include<bits/stdc++.h>
using namespace std;
int findrepeatedelement(int arr[], int n, int k){
priority_queue<int> p;
for(int i = 0; i < n; i++)
p.push(arr[i]);
while(--k)
p.pop();
return p.top();
}
int main(){
int arr[] = {10, 5, 1, 30, 20};
cout<<findrepeatedelement(arr, 5, 3);
return 0;
}
One of the easiest ways to find the first repeated element in the array is to use an unordered set and keep inserting the element in the set until you find the repeated element which is from before present in the set, if present then return the number this will be your first repeated element.
Implementation:
#include<bits/stdc++.h>
using namespace std;
int findrepeatedelement(int arr[], int n){
unordered_set<int> s;
for(int i = 0; i < n; i++){
if(s.find(arr[i]) != s.end())
return arr[i];
else
s.insert(arr[i]);
}
}
int main(){
int arr[] = {10,23,44,23,44,23,12,3,18,19};
cout<<findrepeatedelement(arr, 10);
return 0;
}
One of the easiest approaches to the above problem is to use the XOR operator to find out the missing number in the array from 1 to any number (here 100), taking XOR will lead to the elimination of the repeated integers which are present in the array and from 1 to n, thus printing the result.
Implementation:
#include<bits/stdc++.h>
using namespace std;
int findfirstrepeatedelement(int arr[], int n){
int x1 = arr[0];
int x2 = 1;
for(int i = 1; i < n; i++)
x1 = x1 ^ arr[i];
for(int i = 2; i <= n + 1; i++)
x2 = x2 ^ i;
return (x1 ^ x2);
}
int main()
{
int a[] = {1, 2, 4, 5, 6};
int miss = findfirstrepeatedelement(a, 5);
cout << miss;
return 0;
}
One of the clear implementations of the above problem is that you must count the total number of given key elements in the array and then count the number of the key elements which is present consecutively in the array, if the next element is not the key element then, simply make a counter variable 0, and at last if the value of the counter variable equals the total count then, return true else return false.
Implementation of the above code:
#include<bits/stdc++.h>
using namespace std;
bool checknumbers(int arr[], int key, int n){
int count = 0;
for(int i = 0; i < n; i++){
if(arr[i] == key)
count++;
}
int temp = 1;
for(int i = 0; (i + 1) < n; i++){
if(arr[i] == key && arr[i + 1] == key){
temp++;
if(temp == count)
return true;
}
else
temp = 1;
}
return false;
}
int main(){
int arr[] = {1, 1, 0, 1, 1, 1, 1};
cout<<checknumbers(arr, 1, 7)<<endl;
}
For example, the above code will return false because there are a total of 6 one's but all are not consecutive.
The idea is to use a unordered_set in c++ and remove all the characters which are present in the set.
Implemenation:
#include<bits/stdc++.h>
using namespace std;
void removecharacters(string str1, string str2){
unordered_set<char> s;
for(int i = 0; i < str2.length(); i++)
s.insert(str2[i]);
string st = "";
for(int i = 0; i < str1.length(); i++){
if(s.find(str1[i]) == s.end())
st += str1[i];
}
cout<<st<<endl;
}
int main()
{
char str[] = "geeksforgeeks";
char mask_str[] = "mask";
removecharacters(str, mask_str);
return 0;
}
In the above algorithm, the basic idea used is about the backtracking where we will keep the first character of the string fixed swapping the first character first followed by the other two characters and so on till all possible anagrams are not printed.
- swapnilkant11 June 03, 2019One of the methods is to print all possible permutations of the string.
Implementation:
#include<bits/stdc++.h>
using namespace std;
void swap(char *x, char *y){
int temp = *x;
*x = *y;
*y = temp;
}
void printanagrams(char *str, int l, int r){
if(l == r)
cout<<str<<endl;
else{
for(int i = l; i <= r; i++){
swap((str+l), (str+i));
printanagrams(str, l+1, r);
swap((str+l), (str+i));
}
}
}
int main()
{
char str[] = "ABC";
int n = strlen(str);
printanagrams(str, 0, n-1);
return 0;
}
yes
- swapnilkant11 June 03, 2019For the above algorithm, one needs to check for all the characters present in both the strings if the ASCII value of any one of the characters in string 1 is less than we must return -1 if both the strings have equal length and both are equal then return 0 else return 1.
Implementation:
#include<bits/stdc++.h>
using namespace std;
int findstrings(string str1, string str2){
int count = 0;
transform(str1.begin(), str1.end(), str1.begin(), ::tolower);
transform(str2.begin(), str2.end(), str2.begin(), ::tolower);
int n = str1.length();
int m = str2.length();
if(n > m)
return -1;
for(int i = 0; i < n; i++){
if(str1[i] == str2[i])
count++;
else if((int)str1[i] > (int)str2[i])
return +1;
else
return -1;
}
if(count == n)
return 0;
}
int main(){
string str1 = "abc";
string str2 = "mno";
cout<<findstrings(str1, str2)<<endl;
return 0;
}
One of the most efficient methods is to use a stack for it, push all the characters in the given string from the end position and when there is any space encountered pop all the characters from the stack and concatenate them together along with space at the end to form a string and keep repeating the step until the stack is empty.
Imlementation:
void reversewords(string str){
stack<char> s;
string st = "";
for(int i = str.length() - 1; i >= 0; i--){
if(str[i] == ' '){
while(!s.empty()){
char c = s.top();
s.pop();
st += c;
}
st += str[i];
}
else
s.push(str[i]);
}
while(!s.empty()){
char d = s.top();
s.pop();
st += d;
}
cout<<st<<endl;
}
One of the ways to implement the above problem statement is to use the STL library as implemented below:
void reversestring(string str){
if(str.size() == 0)
return;
reversestring(str.substr(1));
cout<<str[0];
}
For this problem, we have to first define a string which will hold all the alphabets in the order of "a" to "z", we will store all the characters in a hashmap and then we will sort the array of strings according to the order in which the string is defined and then print the result.
Implementation:
#include<bits/stdc++.h>
using namespace std;
map<char, int> h;
bool compare(string x, string y){
for(int i = 0; i < min(x.size(), y.size()); i++){
if(h[x[i]] == h[y[i]])
continue;
return h[x[i]] < h[y[i]];
}
return x.size() < y.size();
}
int main()
{
string str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
vector<string> v = { "ABCDEF", "AA", "BEF",
"A", "AABB" };
for(int i = 0; i < str.length(); i++)
h[str[i]] = i;
sort(v.begin(), v.end(), compare);
for(auto x : v)
cout<<x<<" ";
return 0;
}
For this above problem, one may use unordered set in c++ and insert all the elements of s1 to the set and then keep traversing both the other arrays and check that for the s2 array if all the elements are present and for the s3 array all the elements are not present then return true else return false.
Implementation:
#include<bits/stdc++.h>
using namespace std;
bool findsubsets(int s1[], int n1, int s2[], int n2, int s3[], int n3){
int flag = 0;
int temp = 0;
unordered_set<int> s;
for(int i = 0; i < n1; i++)
s.insert(s1[i]);
for(int j = 0; j < n2; j++){
if(s.find(s2[j]) == s.end()){
flag = -1;
break;
}
}
if(flag != -1)
flag = 1;
for(int j = 0; j < n3; j++){
if(s.find(s3[j]) == s.end()){
temp = 1;
break;
}
}
if(temp != 1)
temp = -1;
if(flag == 1 && temp == 1)
return true;
else
return false;
}
int main()
{
int s1[] = {1, 5, 4, 6, 8, 2};
int s2[] = {5, 8, 2};
int s3[] = {5, 8, 2, 7};
int n1 = sizeof(s1) / sizeof(s1[0]);
int n2 = sizeof(s2) / sizeof(s2[0]);
int n3 = sizeof(s3) / sizeof(s3[0]);
cout<<findsubsets(s1, n1, s2, n2, s3, n3)<<endl;
return 0;
}
For checking that two strings are an anagram of each other, we can use an unordered set in c++ and insert all the characters of the first string and then iterate over the second string and keep checking that the characters in second string must be present in the set if not then both strings are not anagrams of each other else they are.
Implementation:
#include<bits/stdc++.h>
using namespace std;
bool findanagram(string s1, string s2){
unordered_set<char> s;
int n1 = s1.length();
int n2 = s2.length();
transform(s1.begin(), s1.end(), s1.begin(), ::tolower);
transform(s2.begin(), s2.end(), s2.begin(), ::tolower);
for(int i = 0; i < n1; i++)
s.insert(s1[i]);
for(int j = 0; j < n2; j++){
if(s.find(s2[j]) == s.end())
return false;
}
return true;
}
int main()
{
string str1 = "LISTEN";
string str2 = "silent";
cout<<findanagram(str1, str2)<<endl;
return 0;
}
The simple implementation of the above program is to use an unordered set in c++ and first check if the length of the two subset strings from the array has the same length or not if no then return false. If yes, then push all the characters of the string to the set and then compare each character from the other string and if there is any character which does not match with the character in the set return false, else return true.
Implementation:
#include <bits/stdc++.h>
using namespace std;
bool areAnagram(string str1, string str2){
unordered_set<char> s;
int i;
int n = str1.length();
int m = str2.length();
if (n != m)
return false;
for (i = 0; i < n; i++)
s.insert(str1[i]);
for(i = 0; i < m; i++){
if(s.find(str2[i]) == s.end())
return false;
}
return true;
}
void findAllAnagrams(string arr[], int n)
{
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
if (areAnagram(arr[i], arr[j]))
cout << arr[i] << " is anagram of " << arr[j] << endl;
}
int main()
{
string arr[] = {"geeksquiz", "geeksforgeeks", "abcd",
"forgeeksgeeks", "zuiqkeegs"};
int n = sizeof(arr)/sizeof(arr[0]);
findAllAnagrams(arr, n);
return 0;
}
A very simple concept is to use a stack and push all the character values into it until we encounter a space between words, if a space is found concatenate all the character values to a string and pop out all the elements from the stack till it is empty, keep doing the same process until all characters in a string is traversed and finally concatenate the remaining character values to the string and return the string.
Implementation:
#include<bits/stdc++.h>
using namespace std;
string reversestring(string str){
stack<char> s;
string st = "";
for(int i = str.length() - 1; i >= 0; i--){
if(str[i] == ' '){
while(!s.empty()){
st += s.top();
s.pop();
}
st += str[i];
}
else
s.push(str[i]);
}
while(!s.empty()){
st += s.top();
s.pop();
}
return st;
}
int main()
{
string str = "The Sky Is Blue";
cout<<reversestring(str)<<endl;
return 0;
}
A very simple concept is to use a stack and push all the numeric values into it until we encounter an operator, if an operator is found concatenate all the numeric values to a string and pop out all the elements from the stack till it is empty, keep doing the same process until all characters in a string is traversed and finally concatenate the remaining numeric values to the string and return the string
Implementation:
#include<bits/stdc++.h>
using namespace std;
bool checkoperator(char c){
if(c == '-' || c == '+' || c == '/' || c == '*')
return true;
else
return false;
}
string reversestring(string str){
stack<char> s;
string st = "";
for(int i = str.length() - 1; i >= 0; i--){
if(checkoperator(str[i])){
while(!s.empty()){
st += s.top();
s.pop();
}
st += str[i];
}
else
s.push(str[i]);
}
while(!s.empty()){
st += s.top();
s.pop();
}
return st;
}
int main()
{
string str = "1+2*3-20456+980";
cout<<reversestring(str)<<endl;
return 0;
}
One of the most efficient solutions to the above problem could be to use an
1. unordered set in c++.
2. push all the array elements into it.
3. now, one by one pick the elements from the array and calculate the difference between the total sum and the array element and find for the result in the set, if found push the set into the vector, and repeat this step till all the array elements have been processed and then, finally return the vector, which will be you final solution.
Thanks
Could you please elaborate the question a little
Thanks
One of the easiest algorithm for the above problem statement will take the & of the bitwise of the given number and (n - 1) which will result in 0 when the number n is the power of 2 else will result in 1 and then their ! will result in 1 and 0 respectively and && with the number will result in true value if no is power of two else will re turn false:
- swapnilkant11 June 08, 2019Implementation:
#include<bits/stdc++.h>
using namespace std;
bool findpoweroftwo(int x){
return x && (!(x & (x - 1)));
}
int main(){
if(findpoweroftwo(5))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}