Lexicographically compare two given strings and print '-1' if if the first string is less than the second one, print 1 if the second string is less than the first one or print 0 if they are equal. (The letters' case doesn't matter)

first = input().lower()
second = input().lower()
 
if first < second:
    print(-1)
elif second < first:
    print(1)
else:
    print(0)

Time complexity: $$$O(n)$$$ Space Complexity: $$$O(1)$$$

From observing the condition that is given:

n & (n - 1) & (n - 2) & (n - 3) & …. (k) = 0

We can see that we are subtracting one from n every time we use the logical AND between pairs.

Say if n = 5, => n & (n & n — 1) => 5 & (5 & 5 — 1) => 5 & (4) = 4

This can go on until the number becomes zero. If we take a look under the hood and see how the number’s binary representation behaves, we can see that this process is just flipping ones to zero from right to left until the left most bit ,also know as the Most Significant Bit (MSB), is flipped to a zero.

For n = 5

From the above demonstration we can see that the number we have to AND with to flip the MSB is 3 which is conveniently a number we would gate subtracting one from the representation of the MSB. And this representation is just the biggest power of two less that or equal to n. This is also the same with 2 ^ bit_count, where bit count represents the number of bits till upto the MSB (ignoring all leading zeros).

We can achieve this with wide variety of ways. Here are some approaches that you may use, though there might be more ways of doing it.

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

int main() {
    int t, num;
    cin >> t;
    while (t--) {
        cin >> num;
        int nextPowerOfTwo = 1;

        while (nextPowerOfTwo * 2 <= num) {
            nextPowerOfTwo *= 2;
        }

        cout << nextPowerOfTwo - 1 << endl;
    }
}

Time Complexity : $$$O(logn)$$$ Space Complexity : $$$O(1)$$$

t = int(input())

for i in range(t):
    num = int(input())
    while num & (num - 1) :
        num &= num - 1
    print(num - 1)

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

We have people named 1,2,3 .... n. We do also have groups or unions formed based on pairs of nodes given in the input.

So simply the problem is picking one person from each group. Which person in a group? The guy with smallest gold demand.

How do we form the groups from the input? We can use union find algorithm can't we? Or DFS or BFS. I'm going with union-find for no special reason. Well if you have affiliation with BFS or DFS then that also possible.

So after implementing the find(..) and union(..) functions and grouping every node pairs in the input. All we have to do is then picking a person from each group.

If you don't have idea of how to pick, here is how. After unionising the nodes we will know for every node to which group they belong. Usually by the #find(node) function. Then by iterating for each node. We can register the smallest gold for each group. Then print the sum of them

def find(node, parents):
    if parents[node] == node:
        return node
    parents[node] = find(parents[node], parents)
    return parents[node]
 
def union(a, b, parents, rank):
    root_a = find(a, parents)
    root_b = find(b, parents)
 
    if rank[root_a] < rank[root_b]:
        root_a, root_b = root_b, root_a
 
    parents[root_b] = root_a
    rank[root_a] += rank[root_b]
 
 
 
n, m = map(int, input().split())
gold = map(int, input().split())
 
parents = {i:i for i in range(1,n+1)}
rank = {i:1 for i in range(1,n+1)}
 
for _ in range(m):
    a, b = map(int, input().split())
    union(a, b, parents,rank)
 
costs = {} 
for node, cost in enumerate(gold, 1):
    root = find(node, parents)
 
    if root in costs:
        costs[root] = min(costs[root], cost)
    else:
        costs[root] = cost
 
print(sum(costs.values()))

let N : (number of nodes), M : (number of node pairs) Time Complexity: $$$O(M*log(N) + N)$$$, Space Complexity: $$$O(N)$$$

import collections

n, m = map(int, input().split())
visited = set()
golds = list(map(int, input().split()))
graph = [[] for _ in range(n)]
 
for _ in range(m):
  x,y = map(int, input().split())
  graph[x-1].append(y-1)
  graph[y-1].append(x-1)
 
def bfs(x):
  _min = float('inf')
  while queue:
    node = queue.popleft()
    _min = min(_min, golds[node])
 
    for v in graph[node]:
      if v not in visited:
        visited.add(v)
        queue.append(v)
  return _min
 
queue = collections.deque()
 
total = 0
for i in range(n):
  if i not in visited:
    queue.append(i)
    visited.add(i)
    total += bfs(i)
 
print(total)

Time Complexity: $$$O(n)$$$ Space Complexity: $$$O(n)$$$

In this problem we are asked to find the longest three equal substrings called prefix, suffix and obelisk (neither prefix nor suffix). To find the prefix and suffix, let $$$i$$$ (initially $$$i=0$$$) point to the end of the prefix (prefix becomes $$$s[:i+1]$$$) and let $$$j$$$ (initially $$$j=n-1$$$) point to the start of the suffix (suffix becomes $$$s[j:]$$$). But what about obelisk? the time complexity would be too slow if we were to find obelisk after finding prefix and suffix. We can use another pointer $$$k$$$ (initially $$$k=n-2$$$) that points to the start of the obelisk (obelisk becomes $$$s[k:k+i+1]$$$, $$$i+1$$$ is our current string size). The suffix and obelisk's strings should be equal. We can't guarantee that prefix is the same as suffix on every iterations, but obelisk should always be the same as suffix. To solve this problem a sliding window technique can be applied and whenever obelisk is different from suffix slide the window which is $$$(k:k+i+1)$$$ by $$$1$$$ to the left. We do this for every i in 0...n-2 while k > 0. Finally, from all acceptable password variants we choose the longest one.

The above algorithm runs in o(n^2) time complexity. And the expensive operation was checking if two string are equal. There are two string matching algorithms (Robin Karp and KMP algorithms). In solution 1 rolling hash (Robin Karp algorithm) is used to reduce the time complexity to a linear runtime. In solution 2 kmp (Knuth–Morris–Pratt) is used.

Resources to learn about rolling hash Youtube and blog. KMP Youtube and blog

Use three different hash values for suffix, prefix and obelisk. Try to maintain an equal hash value for obelisk and suffix. If the three values are equal, one acceptable password variant is found.

def get_hash(c):
    return 1+ord(c)-ord("a")

def solve(s):
    n = len(s)
    a, curr_a = 31, 1
    mod = 10**9 + 7
    password_idx = -1
    p_hash = s_hash = o_hash = 0 # prefix, suffix and obelisk hash values respectively
    k = n-2 # pointer for obelisk
    for i in range(n-1): # i is pointer for prefix
        j = -i-1 # pointer for suffix
        p_hash = (p_hash + get_hash(s[i])*curr_a) % mod
        s_hash *= a
        s_hash = (s_hash + get_hash(s[j])) % mod
        o_hash *= a
        o_hash = (o_hash + get_hash(s[k])) % mod
        while s_hash != o_hash and k > 0:
            o_hash -= get_hash(s[k+i])*curr_a
            k -= 1
            o_hash *= a
            o_hash = (o_hash + get_hash(s[k])) % mod
        if k == 0: break # since obelisk can't be a prefix
        if p_hash == s_hash:
            password_idx = i
        k -= 1
        curr_a *= a
        curr_a %= mod

    if password_idx != -1:
        return s[:password_idx+1]
    return "Just a legend"

if __name__ == '__main__':
    s = input()
    print(solve(s))

Time complexity: $$$O(n)$$$ Space Complexity: $$$O(1)$$$

Author: nCydready

# This is a kmp solution and a tutorial will be added later
s = input()
 
pattern = [0] * (len(s) + 1)
left, right = 0, 1
 
while right < len(s): # longest proper prefix that also a suffix
    if s[left] == s[right]:
        left += 1
        right += 1
        pattern[right] = left
    elif left > 0:
    	left = pattern[left] 
    else: 
    	right += 1
 
n = pattern.pop()
if n > 0 and n in pattern:
    print(s[:n])
elif pattern[n] > 0:
    print(s[:pattern[n]])
else:
    print('Just a legend')

Time complexity: $$$O(n)$$$ Space Complexity: $$$O(n)$$$