Given an array A[] of size N and a binary array B[] of size N, the task is to check if the array A[] can be converted into a sorted array by swapping pairs (A[i], A[j]) if B[i] is not equal to B[j]. If the array A[] can be sorted, then print “Yes“. Otherwise, print “No“.
Examples:
Input: A[] = {3, 1, 2}, B[] = {0, 1, 1}
Output: Yes
Explanation:
Swap element at position 1 and position 2 of A[] since B[1]!=B[2]. So, A[] = {1, 3, 2}, B[] = {1, 0, 1}
Now, swap element at position 2 and position 3 of A[] since B[2]!=B[3]. So, A[] = {1, 2, 3}. Hence, it is sorted.Input: A[] = {5, 15, 4}, B[] = {0, 0, 0}
Output: No
Approach: The problem can be solved based on the following observations:
If at least two elements of the array, B[] are different, then it is possible to swap any two elements of the array A[].
Follow the steps below to solve the problem:
- Check if the given array A[] is already sorted in ascending order or not. If found to be true, then print “Yes”.
- Otherwise, count the number of 1s and 0s present in the array B[].
- If the array B[] contains at least one 0 and one 1, then print “Yes”.
- Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ Program for above approach#include <bits/stdc++.h>using namespace std;// Function to check if array, A[] can be converted // into sorted array by swapping (A[i], A[j]) if B[i] is// not equal to B[j]bool checkifSorted(int A[], int B[], int N){ // Stores if array A[] is sorted // in descending order or not bool flag = false; // Traverse the array A[] for (int i = 0; i < N - 1; i++) { // If A[i] is greater than A[i + 1] if (A[i] > A[i + 1]) { // Update flag flag = true; break; } } // If array is sorted // in ascending order if (!flag) { return true; } // count = 2: Check if 0s and 1s // both present in the B[] int count = 0; // Traverse the array for (int i = 0; i < N; i++) { // If current element is 0 if (B[i] == 0) { // Update count count++; break; } } // Traverse the array B[] for (int i = 0; i < N; i++) { // If current element is 1 if (B[i] == 1) { count++; break; } } // If both 0s and 1s are present // in the array if (count == 2) { return true; } return false;}// Driver Codeint main(){ // Input array A[] int A[] = { 3, 1, 2 }; // Input array B[] int B[] = { 0, 1, 1 }; int N = sizeof(A) / sizeof(A[0]); // Function call bool check = checkifSorted(A, B, N); // If true,print YES if (check) { cout << "YES" <<endl; } // Else print NO else { cout << "NO" <<endl; } return 0;} |
Java
// Java program of the above approachimport java.io.*;class GFG { // Function to check if array, A[] can be converted // into sorted array by swapping (A[i], A[j]) if B[i] // not equal to B[j] static boolean checkifSorted(int A[], int B[], int N) { // Stores if array A[] is sorted // in descending order or not boolean flag = false; // Traverse the array A[] for (int i = 0; i < N - 1; i++) { // If A[i] is greater than A[i + 1] if (A[i] > A[i + 1]) { // Update flag flag = true; break; } } // If array is sorted // in ascending order if (!flag) { return true; } // count = 2: Check if 0s and 1s // both present in the B[] int count = 0; // Traverse the array for (int i = 0; i < N; i++) { // If current element is 0 if (B[i] == 0) { // Update count count++; break; } } // Traverse the array B[] for (int i = 0; i < N; i++) { // If current element is 1 if (B[i] == 1) { count++; break; } } // If both 0s and 1s are present // in the array if (count == 2) { return true; } return false; } // Driver Code public static void main(String[] args) { // Input array A[] int A[] = { 3, 1, 2 }; // Input array B[] int B[] = { 0, 1, 1 }; int N = A.length; // Function call boolean check = checkifSorted(A, B, N); // If true,print YES if (check) { System.out.println("YES"); } // Else print NO else { System.out.println("NO"); } }} |
Python3
# Python program of the above approach # Function to check if array, A[] can be converted # into sorted array by swapping (A[i], A[j]) if B[i]# not equal to B[j]def checkifSorted(A, B, N): # Stores if array A[] is sorted # in descending order or not flag = False # Traverse the array A[] for i in range( N - 1): # If A[i] is greater than A[i + 1] if (A[i] > A[i + 1]): # Update flag flag = True break # If array is sorted # in ascending order if (not flag): return True # count = 2: Check if 0s and 1s # both present in the B[] count = 0 # Traverse the array for i in range(N): # If current element is 0 if (B[i] == 0): # Update count count += 1 break # Traverse the array B[] for i in range(N): # If current element is 1 if B[i]: count += 1 break # If both 0s and 1s are present # in the array if (count == 2): return True return False# Driver Code# Input array A[]A = [ 3, 1, 2 ]# Input array B[]B = [ 0, 1, 1 ]N = len(A)# Function callcheck = checkifSorted(A, B, N)# If true,print YESif (check): print("YES") # Else print NOelse: print("NO") # This code is contributed by rohitsingh07052 |
C#
// C# program of the above approachusing System;public class GFG{ // Function to check if array, A[] can be converted // into sorted array by swapping (A[i], A[j]) if B[i] // not equal to B[j] static bool checkifSorted(int []A, int []B, int N) { // Stores if array A[] is sorted // in descending order or not bool flag = false; // Traverse the array A[] for (int i = 0; i < N - 1; i++) { // If A[i] is greater than A[i + 1] if (A[i] > A[i + 1]) { // Update flag flag = true; break; } } // If array is sorted // in ascending order if (!flag) { return true; } // count = 2: Check if 0s and 1s // both present in the B[] int count = 0; // Traverse the array for (int i = 0; i < N; i++) { // If current element is 0 if (B[i] == 0) { // Update count count++; break; } } // Traverse the array B[] for (int i = 0; i < N; i++) { // If current element is 1 if (B[i] == 1) { count++; break; } } // If both 0s and 1s are present // in the array if (count == 2) { return true; } return false; } // Driver Code public static void Main(string[] args) { // Input array A[] int []A = { 3, 1, 2 }; // Input array B[] int []B = { 0, 1, 1 }; int N = A.Length; // Function call bool check = checkifSorted(A, B, N); // If true,print YES if (check) { Console.WriteLine("YES"); } // Else print NO else { Console.WriteLine("NO"); } }}// This code is contributed by AnkThon |
Javascript
<script>// javascript program of the above approach // Function to check if array, A can be converted // into sorted array by swapping (A[i], A[j]) if B[i] // not equal to B[j] function checkifSorted(A , B , N) { // Stores if array A is sorted // in descending order or not var flag = false; // Traverse the array A for (i = 0; i < N - 1; i++) { // If A[i] is greater than A[i + 1] if (A[i] > A[i + 1]) { // Update flag flag = true; break; } } // If array is sorted // in ascending order if (!flag) { return true; } // count = 2: Check if 0s and 1s // both present in the B var count = 0; // Traverse the array for (i = 0; i < N; i++) { // If current element is 0 if (B[i] == 0) { // Update count count++; break; } } // Traverse the array B for (i = 0; i < N; i++) { // If current element is 1 if (B[i] == 1) { count++; break; } } // If both 0s and 1s are present // in the array if (count == 2) { return true; } return false; } // Driver Code // Input array A var A = [ 3, 1, 2 ]; // Input array B var B = [ 0, 1, 1 ]; var N = A.length; // Function call var check = checkifSorted(A, B, N); // If true,print YES if (check) { document.write("YES"); } // Else print NO else { document.write("NO"); }// This code contributed by Rajput-Ji</script> |
Output
YES
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach 2:
Here’s another approach to solve the problem:
- Create a vector of pairs to store both the elements and their respective types (0 or 1) from arrays A and B.
- Sort the vector in descending order based on the elements of A.
- Traverse the sorted vector and check if the type of the current element is 0. If it is, then we have found the first unsorted element that needs to be swapped.
- Traverse the rest of the vector and check if any other element with type 1 is present. If it is, then swap the elements and return “YES”. If not, return “NO”.
Here’s the code for the same approach:
C++
#include <bits/stdc++.h>using namespace std;bool checkIfSorted(int A[], int B[], int N) { vector<pair<int, int>> vec; for (int i = 0; i < N; i++) { vec.push_back({A[i], B[i]}); } sort(vec.rbegin(), vec.rend()); int unsortedIndex = -1; for (int i = 0; i < N - 1; i++) { if (vec[i].second > vec[i + 1].second) { unsortedIndex = i; break; } } if (unsortedIndex == -1) { return true; } for (int i = unsortedIndex + 1; i < N; i++) { if (vec[i].second == 1) { swap(vec[unsortedIndex].first, vec[i].first); break; } } for (int i = 0; i < N - 1; i++) { if (vec[i].first > vec[i + 1].first) { return false; } } return true;}int main() { int A[] = {3, 1, 2}; int B[] = {0, 1, 1}; int N = sizeof(A) / sizeof(A[0]); bool check = checkIfSorted(A, B, N); if (check) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0;} |
Java
// Nikunj Sonigaraimport java.util.*;class Main { // This function checks if the given arrays A and B can be sorted by swapping // elements in such a way that the resulting array is sorted in ascending order. static boolean checkIfSorted(int[] A, int[] B, int N) { List<Pair<Integer, Integer>> vec = new ArrayList<>(); // Create a list of pairs, where each pair consists of elements from arrays A and B. for (int i = 0; i < N; i++) { vec.add(new Pair<>(A[i], B[i])); } // Sort the list of pairs in descending order based on the A values. vec.sort((a, b) -> Integer.compare(b.getKey(), a.getKey())); int unsortedIndex = -1; // Find the index where the list becomes unsorted in terms of B values. for (int i = 0; i < N - 1; i++) { if (vec.get(i).getValue() > vec.get(i + 1).getValue()) { unsortedIndex = i; break; } } if (unsortedIndex == -1) { return true; // If the list is already sorted by B values, return true. } // Find an element with B value equal to 1 and swap it with the unsorted element. for (int i = unsortedIndex + 1; i < N; i++) { if (vec.get(i).getValue() == 1) { Collections.swap(vec, unsortedIndex, i); break; } } // Check if the list is sorted in ascending order by A values after the swap. for (int i = 0; i < N - 1; i++) { if (vec.get(i).getKey() > vec.get(i + 1).getKey()) { return false; // If not sorted, return false. } } return true; // If sorted after the swap, return true. } public static void main(String[] args) { int[] A = {3, 1, 2}; int[] B = {0, 1, 1}; int N = A.length; boolean check = checkIfSorted(A, B, N); if (check) { System.out.println("YES"); // Output "YES" if the arrays can be sorted. } else { System.out.println("NO"); // Output "NO" if the arrays cannot be sorted. } } // Definition of the Pair class for storing pairs of elements. static class Pair<K, V> { private final K key; private final V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; } }} |
Python3
# Python code for the above approachdef checkIfSorted(A, B, N): vec = [] # Create a list of tuples containing elements from A and B for i in range(N): vec.append([A[i], B[i]]) # Sort the list in descending order based on the first element of each tuple vec.sort(key=lambda x: x[0], reverse=True) unsortedIndex = -1 # Find the first index where the second element of the tuple is greater than the second element of the next tuple for i in range(N - 1): if vec[i][1] > vec[i + 1][1]: unsortedIndex = i break # If no such index is found, the list is already sorted if unsortedIndex == -1: return True # Swap the first element of the unsorted tuple with the first element of the next tuple with second element equal to 1 for i in range(unsortedIndex + 1, N): if vec[i][1] == 1: vec[unsortedIndex][0], vec[i][0] = vec[i][0], vec[unsortedIndex][0] break # Check if the list is sorted in ascending order based on the first element of each tuple for i in range(N - 1): if vec[i][0] > vec[i + 1][0]: return False return TrueA = [3, 1, 2]B = [0, 1, 1]N = len(A)check = checkIfSorted(A, B, N)if check: print("YES")else: print("NO")# This code is contributed by Kanchan Agarwal |
C#
using System;using System.Collections.Generic;using System.Linq;class Program{ static bool CheckIfSorted(int[] A, int[] B, int N) { List<Tuple<int, int>> vec = new List<Tuple<int, int>>(); // Create a list of tuples containing elements from A and B for (int i = 0; i < N; i++) { vec.Add(new Tuple<int, int>(A[i], B[i])); } // Sort the list in descending order based on the first element of each tuple vec = vec.OrderByDescending(x => x.Item1).ToList(); int unsortedIndex = -1; // Find the first index where the second element of the tuple is // greater than the second element of the next tuple for (int i = 0; i < N - 1; i++) { if (vec[i].Item2 > vec[i + 1].Item2) { unsortedIndex = i; break; } } // If no such index is found, the list is already sorted if (unsortedIndex == -1) { return true; } // Swap the first element of the unsorted tuple with the first element of the // next tuple with the second element equal to 1 for (int i = unsortedIndex + 1; i < N; i++) { if (vec[i].Item2 == 1) { Tuple<int, int> temp = vec[unsortedIndex]; vec[unsortedIndex] = Tuple.Create(vec[i].Item1, vec[unsortedIndex].Item2); vec[i] = Tuple.Create(temp.Item1, vec[i].Item2); break; } } // Check if the list is sorted in ascending order based on the first element of each tuple for (int i = 0; i < N - 1; i++) { if (vec[i].Item1 > vec[i + 1].Item1) { return false; } } return true; } static void Main(string[] args) { int[] A = { 3, 1, 2 }; int[] B = { 0, 1, 1 }; int N = A.Length; bool check = CheckIfSorted(A, B, N); if (check) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } }} |
Javascript
function checkIfSorted(A, B, N) { let vec = []; for (let i = 0; i < N; i++) { vec.push([A[i], B[i]]); } vec.sort((a, b) => b[0] - a[0]); let unsortedIndex = -1; for (let i = 0; i < N - 1; i++) { if (vec[i][1] > vec[i + 1][1]) { unsortedIndex = i; break; } } if (unsortedIndex === -1) { return true; } for (let i = unsortedIndex + 1; i < N; i++) { if (vec[i][1] === 1) { [vec[unsortedIndex][0], vec[i][0]] = [vec[i][0], vec[unsortedIndex][0]]; break; } } for (let i = 0; i < N - 1; i++) { if (vec[i][0] > vec[i + 1][0]) { return false; } } return true;}let A = [3, 1, 2];let B = [0, 1, 1];let N = A.length;let check = checkIfSorted(A, B, N);if (check) { console.log("YES");} else { console.log("NO");} |
Output:
YES
Time Complexity: O(N log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
