Editorial for Let's Code Round 1

This is the official Editorial for the contest held on April 15 2021 at HackerRank Platform.
Link for the Contest

1 Like

Editorial for Brute Force

This is an Implementation(Just do what the problem says) Based Problem. For all K length passwords there are 3^K total different passwords that can be made given the 3 characters.

One way to find all the possible passwords is to take a particular position and fix the character you want at that position and then continue the same for the rest of the positions.

The general and more intuitive method to do it would be using recursion to solve it. Start with the first position and then fix a character at that position and then recur for the next position and so on until the length of the password generated by recursion reaches K.

#include <bits/stdc++.h>
using namespace std;

void solve(vector<char> letters, vector<string>& ans, string p,int n, int k){
    if (k == 0){
        ans.push_back(p);
        return;
    }
    for (int i = 0; i < n; i++){
        string prefix;
        prefix = p+(letters[i]);
        solve(letters, ans, prefix, n, k - 1);
    }
}

int main(){

    int n;
    cin>>n;
    
    vector<char> letters;
    for(int i=0; i<3; i++)  letters.push_back('1'+i);
    vector<string> ans;
    solve(letters, ans, "", 3, n);
    
    cout<<ans.size()<<endl;
    for(auto x:ans){
        cout<<x<<"\n";
    }
    return 0;
}

Time Complexity : O(3^K)

1 Like

Editorial for Word counter

This problem only focussed upon how to tackle whitespaces ' ', because words on a single line are seperated by whitespaces(normally unless you have a habit of screwing up). This problem could have been further made a little difficult by asking to find the number of words across multiple lines. Then you would also have to deal with the newline character ‘\n’.

There is a simple solution that handles both of these cases quite well.

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    int ans = 0;
    while(cin>>s) ans++;
    cout<<ans;
    return 0;
}

Time Complexity : O(words) - Only the time taken to receive the input

1 Like

Editorial for Sum it Up!

The problem reduces to finding the largest and the second largest number. It can be done in many ways. A straight forward solution is to sort the array and find out the largest two elements from the array. Then add them and print the answer.

#include <bits/stdc++.h>
using namespace std;

int main(){

    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0; i<n; i++){
      cin>>v[i];
    }
    sort(v.begin(), v.end(), greater<int>());
    int ans = v[0]+v[1];
    cout<<ans<<"\n";
    
    return 0;
}

Time Complexity : O(nlogn)

1 Like

Editorial for Palindrome Worthy

The first thing to observe is that the order of characters in the given word doesn’t matters because the letters can be rearranged any number of times.

Then this problem can be split into two subproblems based upon an Observation.
Observation :

  1. All the characters present in a palindrome of even length occur in multiples of 2(even number of times), the reason being for every character at the k-th from the start of the word it must also be present at the k-th position from the end of the word(i.e., no character should occur odd number of times).
  2. For palindromes of odd length too the above Observation will work with an extra case for the character that occurs exactly in the middle, for that character should appear exactly odd times in the palindrome
Forward        Reverse
Indexing       Indexing

a b a b a     a b a b a
1 2 3 4 5     5 4 3 2 1 

We can make a frequency array for all the characters present in the string and check
it on the basis of above two observations.

#include <bits/stdc++.h>

using namespace std;



int main()
{
    // Write Complete code here.
    int t;
    cin>>t;
    for(int i=0; i<t; i++){
      string s;
      cin>>s;
      map<char, int> ma;
      int n = s.size();
      for(int i=0; i<n; i++){
        ma[s[i]]++;
      }
      int odd = 0;
      for(auto x:ma){
        if(x.second&1){
          odd++;
        }
      }
      if(n&1){
        
        if(odd == 1){
          cout<<"YES\n";
        }else{
          cout<<"NO\n";
        }
      }else{
        if(odd == 0){
          cout<<"YES\n";
        }else{
          cout<<"NO\n";
        }
      }
    }
    return 0;
}

Time Complexity - O(nlogn) per test case for this implementation, but can be improved to O(n) by using a frequency array with some extra memory.

1 Like