An array A of size N is called stable if all the elements in it are equal. We need to find the minimum number of operations to convert an array into a stable array if an operation can be any one of the following:
Select prefix A[1,2 \dots , k] where A_k >= A_i for all 1 \leq i \leq k and perform A_i = A_k for all 1 \leq i \leq k.
Select any segment A[L, \dots, R] and cyclically shift the elements in this segment to the left keeping other elements in the array unchanged.
EXPLANATION:
If initially all the elements in the array are equal, obviously the answer is 0.
Let max be the maximum element in the array and let it be at index ind. (If multiple indices are possible, take ind as the maximum among them).
If ind =N, we can just perform the first operation taking k = N and convert all the elements in the array equal to max.
If ind \lt N, we need to perform a total of 2 operations. First, we need to apply operation 2 on the segment A[ind,\dots, N]. This sends the value at index ind( i.e, max) to index N. Now we can perform operation 1 taking k = N, and convert all the elements in the array equal to max.
TIME COMPLEXITY:
O(N) for each testcase.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int tests;
cin >> tests;
while(tests--) {
int n;
cin >> n;
vector<int> a(n);
for (int i=0; i<n; i++) {
cin >> a[i];
}
bool allEqual = true;
int max1 = a[0];
for (int i=0; i<n; i++) {
if (i>0 && a[i]!=a[i-1]) {
allEqual = false;
}
max1 = max(max1, a[i]);
}
if (allEqual) {
cout << 0 << endl;
}
else if (a[n-1] == max1) {
cout << 1 << endl;
}
else {
cout << 2 << endl;
}
}
return 0;
}
Setter's solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while (t--){
int n;
cin>>n;
vector<int>a(n);
int maxi = 0;
int elem = 0;
bool isEqual = true;
for (int i = 0;i<n;i++){
cin>>a[i];
maxi = max(maxi,a[i]);
if (i == 0)
elem = a[0];
else {
if (a[i] != elem)
isEqual = false;
}
}
if (isEqual)cout<<0<<endl;
else if (maxi == a[n - 1])cout<<1<<endl;
else cout<<2<<endl;
}
}
Tester's solution
def main():
for _ in range(int(input())):
n=int(input())
a=[int(x) for x in input().split()]
if len(set(a))==1:
print(0)
elif max(a)==a[-1]:
print(1)
else:
print(2)
main()
Please comment below if you have any questions, alternate solutions, or suggestions.
sir i have done the logic but my question is that i have done a liitle different approach in the case where max is not in the last position then according to me we need to first do the 1st operation then all the element before max will be max then by rotating once we can get the max at last position so after that we can again do the 1st operation then we will get the stable array but u have done 2 operation so how is it possible in 2 moves
The first time you use the 2nd operation to rotate the subarray and bring the largest element at the end. The second time you use the first operation to change all elements to the same as largest. For when ind<N.
@nj_code Because you output 3 if the first or last element isn’t max but the maximum number of steps needed is 2 and not 3.
For example: If the maximum number is in any middle position it can simply be brought to the last position by the second operation and apply first operation resulting in balanced condition. So, maximum steps needed is 2 and not 3.
I did the same thing in my code (in C language), but for some reason, I got WA in task 2. My solution was the following -
#include <stdio.h>
int main(void) {
// your code goes here
int t, n, a[100], i, max, j;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(i=0; i<n; i++){
scanf("%d", &a[i]);
}
max=a[0];
if(n>1){
for(i=1; i<n; i++){
if(a[i]>=max){
max=a[i];
j=i;
}
}
}
if(max==a[0]) printf("0\n");
else if(j==n-1) printf("1\n");
else printf("2\n");
}
return 0;
}
The if statement finds the value of the index of the maximum value. If the max variable is still a[0] then its an array with equal values hence 0 is printed. Otherwise if(j==n-1) conditional prints 1 in case the max value is at the end, and the final else statement prints 2 if none of the above conditions are satisfied.
can someone tell me whats wrong in my solution ?
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner ob=new Scanner(System.in);
int t=ob.nextInt();
for (int i=1;i<=t;i++)
{
int n=ob.nextInt();
int a[]=new int[n];
for (int k=0;k<n;k++)
{
a[k]=ob.nextInt();
}
int c=0;
for (int j=0;j<n-1;j++)
{
if(a[j]==a[n-1])
c=1;
else
{
c=0;
break;
}
}
if(c==1)
System.out.println(“0”);
else
{
int d=0;
int large=a[0];
for(int l=0;l<n;l++)
{
if(a[l]>large)
{
large=a[l];
d=l;
}
}
if(large==a[n-1])
System.out.println(“1”);
else
System.out.println(“2”);
}
}
}
}
Hey Everyone! so I did this question in exact same before I read this editorial but unfortunately I’m receiving “WA” in CASE 2. Can somebody suggest me what am I doing wrong. P.S: - I’ve written comments so it won’t be difficult for you to understand what logic I’ve used where.
void test(){
int n;
cin>>n;
int arr[n];
for(int i=0; i<n; i++){
cin>>arr[i];
}
/storing maximum element and its index as well as checking if all elements are same or not/
int maxi=0,idx=0,count=0;
for(int i=0; i<n; i++){
/* condition to check if max element repeats itself or all elements are same*/
if(maxi == arr[i]){
count++;
idx = i;
}
// for finding max element
if(maxi < arr[i]){
maxi = arr[i];
idx=i;
}
}
// if all elements are same
if((count == n) && (maxi == arr[n-1])){
cout<<0<<"\n";
}// if max element is at the end ie: - nth index
else if(maxi == arr[n-1]){
cout<< n-1-count <<"\n";
}// if max element is present somewhere between
else{
maxi = 2*(n-1) - idx - count;
cout<<maxi<<"\n";
}
}
int main(){
int t;
cin>>t;
while(t–){
test();
}
return 0;
}
Thank you in advance whosoever helps me🙂
