fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. int minMutations(string alpha) {
  9.     int n = alpha.size();
  10.     vector<vector<int>> dp(n + 1, vector<int>(2, INT_MAX)); // dp[i][j]: min mutations to convert alpha[0...i-1] to omega, considering mutation j at position i
  11.  
  12.     // Base case: converting empty string to omega requires 0 mutations
  13.     dp[0][0] = dp[0][1] = 0;
  14.  
  15.     // Dynamic programming to fill the dp table
  16.     for (int i = 1; i <= n; ++i) {
  17.         if (alpha[i - 1] == 'A') {
  18.             dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + 1);
  19.             dp[i][1] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 1);
  20.         } else {
  21.             dp[i][0] = min(dp[i - 1][0] + 1, dp[i - 1][1]);
  22.             dp[i][1] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 1);
  23.         }
  24.     }
  25.  
  26.     // The minimum mutations required to convert alpha to omega is the minimum value in the last row of dp table
  27.     return min(dp[n][0], dp[n][1]);
  28. }
  29.  
  30. int main() {
  31.     string alpha;
  32.     cout << "Enter the DNA structure alpha: ";
  33.     cin >> alpha;
  34.  
  35.     int result = minMutations(alpha);
  36.     if (result == INT_MAX) {
  37.         cout << "Omega cannot be synthesized from alpha.";
  38.     } else {
  39.         cout << "Minimum mutations required: " << result;
  40.     }
  41.  
  42.     return 0;
  43. }
  44.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
AAABBBAAABBB
stdout
copy 
Enter the DNA structure alpha: Minimum mutations required: 4
https://ideone.com/aJAy3T
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!