HackerEarth_Codemonk_solution_Cyclic-shift.cpp

// The problem description can be found here... https://youtu.be/k4Nn33QiZ3M

#include <bits/stdc++.h>

// Cyclic shift the std::string to left for 1 bit
void CyclicShiftLeft1(std::string& bit_str) {
  bit_str.push_back(bit_str[0]);
  bit_str.erase(0, 1);
  return;
}

// Cyclic shift the std::string to left for N bit
void CyclicShiftLeftN(std::string& bit_str, long long N) {
  bit_str.append(bit_str.substr(0, N));
  bit_str.erase(0, N);
  return;
}

int main() {
  long long test_cases;
  std::cin >> test_cases;

  for (long long T = 0; T < test_cases; ++T) {
    long long num_bit, num_match;
    std::cin >> num_bit;
    std::cin >> num_match;

    std::string bit_str;
    std::cin >> bit_str;

    std::string max_bit_str = bit_str;
    long long max_i_1st = 0;

    // Finds how many times to rotate to get the maximum value ("max_i_1st") by rotating one by one.
    // The "bit_str" can be compared directly in string type (no need to convert string to int).
    for (long long i = 0; i < num_bit; ++i) {
      if (max_bit_str < bit_str) {
        max_bit_str = bit_str;
        max_i_1st = i;
      }
      CyclicShiftLeft1(bit_str);
    }

    // Now the "bit_str" is in the original position because it is rotated "num_bit" times.
    // So rotates "max_i_1st" times to prepare for finding how many times to rotate to meet the maximum value again ("max_i_2nd").
    if (0 < max_i_1st) {
      CyclicShiftLeftN(bit_str, max_i_1st);
    }

    // Finds how many times to rotate to meet the maximum value again ("max_i_2nd") by rotating one by one.
    long long max_i_2nd = 0;
    for (long long i = 0; i < num_bit; ++i) {
      CyclicShiftLeft1(bit_str);
      if (max_bit_str == bit_str) {
        max_i_2nd = (i + 1);
        break;
      }
    }

    // The number of rotations to get the maximum value for the 1st time ("max_i_1st") and
    // the number of rotations to meet the maximum value for the 2nd time ("max_i_2nd") is different.
    // However, the number of rotations to meet the maximum value for
    // the 3rd time ("max_i_3rd") and the 4th time ("max_i_4th") and ... the Nth time ("max_i_Nth")
    // is SAME as the 2nd time ("max_i_2nd").
    // So we can calculate the final number of rotations without for-loop anymore.
    long long num_rotate_sum = max_i_1st + (num_match - 1) * max_i_2nd;

    std::cout << num_rotate_sum << std::endl;

    /**********************************************
    (Example 1)

    bit_str = "10101"
    -------------------------------------
    max_i_1st = 4: "10101" ---> "11010"
    max_i_2nd = 5: "11010" ---> "11010"
    max_i_3rd = 5: "11010" ---> "11010"
    max_i_4th = 5: "11010" ---> "11010"
      :
      :
    **********************************************/

    /**********************************************
    (Example 2)

    bit_str = "010101"
    -------------------------------------
    max_i_1st = 1: "010101" ---> "101010"
    max_i_2nd = 2: "101010" ---> "101010"
    max_i_3rd = 2: "101010" ---> "101010"
    max_i_4th = 2: "101010" ---> "101010"
      :
      :
    **********************************************/
  }

  return 0;
}