CODEWITHSUNDEEP
c++
Kakashi Sasuke
Kakashi Sasuke

Reputation: 11

How to check if this make a non-increasing sequence or not.

I was given a c++ task to receive a string of numbers.
What I have to do is to move the first digit of that number into the last digit.
for example if number is 1234 it should be 2341 like this.
What I have also to do is to make the sequence of numbers non-increasing.
For better understanding here is what I have to do:
Input:
1934
7815
1894
6518
3281

In the first sample, we will do the following moves:

1 move on x1 : 1934 -> 9341
1 move on x2 : 7815 -> 8157
3 move on x3 : 1894 -> 8941 -> 9418 -> 4189
2 move on x4 : 6518 -> 5186 -> 1865
3 move on x5 : 3281 -> 2813 -> 8132 -> 1328
The final sequence will be 9341 ≥ 8157 ≥ 4189 ≥ 1865 ≥ 1328.

If it's possible to make a non-increasing sequence like this, the program should print yes, otherwise I should print no.
Here is what I have tried: 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {


    string s[5];

     for (int i = 0; i < 5; i++)
    {
        cin >> s[i];
    }
    for (int j = 0; j < 5; j++)
{
            rotate(s[j].begin(), s[j].begin() + 1, s[j].end());

        }
    for (int j = 2; j < 5; j++){
        while (s[j-1] <= s[j]){
                rotate(s[j].begin(), s[j].begin() + 1, s[j].end());



        }

    }

        for (int i = 0; i < 5; i++)
        cout << s[i] << endl;
}

I did all the moves, then printed them, I don't know how to check if it is possible to make a non-increasing sequence or not. Also with my logic the while loop could be infinity loop if I can't make a non-increasing sequence, How to fix that? Thanks.

Upvotes: 1

Views: 245

Answers (1)

bolov
bolov

Reputation: 75697

This is one way to solve this:

  • rotate the first number to the largest possible value.

    e.g. for the number 1894 there are 4 possible rotations: {1894, 8941, 9418, 4189}. The largest one is 9418.

  • for the rest of the numbers rotate them to the largest possible value that is equal or less than the chosen rotation for the previous number. If there is no such rotation then sequence is not possible.

For your example:

  • 1934: the largest rotation is 9341
  • 7815: the largest rotation <= 9341 is 8157
  • 1894: the largest rotation <= 8157 is 4189
  • 6518: the largest rotation <= 4189 is 1865
  • 3281: the largest rotation <= 1865 is 1328

Upvotes: 1

Related Questions