#PROBLEM LINK:
[problem][1]Author: Yasha Jadwani
Tester : Prabhsimran Kaur
Editorialist: Prabhsimran Kaur
DIFFICULTY :
Simple
PREREQUISITES :
Math
PROBLEM:
In this problem, we have-
-
Integer T that denotes the number of test cases.
-
In next line have an integer N. The valid array can take the form 1 to N or any of its circular arrangement.
-
Further there are T lines each with an instance of copied array that we need to verify.
So, we have to calculate the cheat number i.e. number of digits that have been displaced from their correct position in the copied array.
EXPLANATION:
-
Now, consider the following example to understand the meaning of circular arrangement for array of integers 1 to N.
e.g.N=5
than the possible circular arrangements are:
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4 -
The problem can easily be solved by using ‘for’ and ‘while’ loops and than performing comparisons.
All we have to do is ,firstly, save the first element of array in some other variable.
Than, incrementing it’s value and comparing with the integer at the next index of array and so on.
If the values are unequal, we increment the counter by 1 i.e. we found a cheated number. -
For e.g
If copied array is 41523
We store 4 in some variable ‘s’.
On incrementing value of ‘s’ that will become 5 and comparing with next array value i.e. 1 ,we find that both are not equal so we increment the counter by 1.
Again we increment value of ‘s’ but now it will be 1,because we are following circular arrangement and maximum size of array is 5. Comparing it with next array value we got to know that both are unequal. So, again increment counter by 1.
Next two array values matches with the incremented value of ‘s’, so no increment in counter.
Total number of cheated digits=2.
SETTER’S SOLUTION:
The Solution of the problem can be viewed
#include<iostream>
using namespace std;
int main()
{
long t,n,s,c,j;
scanf(“%d\n%d”,&t,&n);
while(t--)
{
int a[n];
c=0;
for(j=0;j<n;j++)
scanf(“%d”,&a[j]);
s=a[0];
j=1;
while(s<n)
{
s++;
if(a[j]!=s)
c++;
j++;
}
s=0;
while(j<=n-1)
{
s++;
if(a[j]!=s)
c++;
j++;
}
printf(“%d\n”,c);
}
return 0;
}