All Courses
AI Career Planner
1:1 Coaching/Mentoring
Job Board
SQL
HTML/CSS/JS
Coding
Settings
LogoutHello Everyone,
Given an array, A of size N consisting of elements 1 to N. A boolean array B consisting of N-1 elements indicates that if B[i] is 1, then A[i] can be swapped with A[i+1].
Find out if A can be sorted by swapping elements.
Examples:
Input : A[] = {1, 2, 5, 3, 4, 6}
B[] = {0, 1, 1, 1, 0}
Output : A can be sorted
We can swap A[2] with A[3] and then A[3] with A[4].
Input : A[] = {2, 3, 1, 4, 5, 6}
B[] = {0, 1, 1, 1, 1}
Output : A can not be sorted
We can not sort A by swapping elements as 1 can never be swapped with A[0]=2.
Here we can swap only A[i] with A[i+1]. So to find whether array can be sorted or not. Using boolean array B we can sort array for a continuous sequence of 1 for B. At last, we can check, if A is sorted or not.
import java.util.Arrays;
// Java program to test whether an array
// can be sorted by swapping adjacent
// elements using boolean array
class GFG {
// Return true if array can be
// sorted otherwise false
static boolean sortedAfterSwap( int A[],
boolean B[], int n)
{
int i, j;
// Check bool array B and sorts
// elements for continuous sequence of 1
for (i = 0 ; i < n - 1 ; i++) {
if (B[i]) {
j = i;
while (B[j]) {
j++;
}
// Sort array A from i to j
Arrays.sort(A, i, 1 + j);
i = j;
}
}
// Check if array is sorted or not
for (i = 0 ; i < n; i++) {
if (A[i] != i + 1 ) {
return false ;
}
}
return true ;
}
// Driver program to test sortedAfterSwap()
public static void main(String[] args)
{
int A[] = { 1 , 2 , 5 , 3 , 4 , 6 };
boolean B[] = { false , true , true , true , false };
int n = A.length;
if (sortedAfterSwap(A, B, n)) {
System.out.println( "A can be sorted" );
}
else {
System.out.println( "A can not be sorted" );
}
}
}
Output:
A can be sorted
Alternative Approach
Here we discuss a very intuitive approach which too gives the answer in O(n) time for all cases. The idea here is that whenever the binary array has 1, we check if that index in array A has i+1 or not. If it does not contain i+1, we simply swap a[i] with a[i+1].
The reason for this is that the array should have i+1 stored at index i. And if at all the array is sortable, then the only operation allowed is swapping. Hence, if the required condition is not satisfied, we simply swap. If the array is sortable, swapping will take us one step closer to the correct answer. And as expected, if the array is not sortable, then swapping would lead to just another unsorted version of the same array.
// Java program to test whether an array
// can be sorted by swapping adjacent
// elements using boolean array
class GFG
{
// Return true if array can be
// sorted otherwise false
static int sortedAfterSwap( int [] A,
int [] B, int n)
{
int t = 0 ;
for ( int i = 0 ; i < n - 1 ; i++)
{
if (B[i] != 0 )
{
if (A[i] != i + 1 )
t = A[i];
A[i] = A[i + 1 ];
A[i + 1 ] = t;
}
}
// Check if array is sorted or not
for ( int i = 0 ; i < n; i++)
{
if (A[i] != i + 1 )
return 0 ;
}
return 1 ;
}
// Driver Code
public static void main(String[] args)
{
int [] A = { 1 , 2 , 5 , 3 , 4 , 6 };
int [] B = { 0 , 1 , 1 , 1 , 0 };
int n = A.length;
if (sortedAfterSwap(A, B, n) == 0 )
System.out.println( "A can be sorted" );
else
System.out.println( "A can not be sorted" );
}
}
Output:
A can be sorted