Given an array arr[] consisting of 2*N integers, the task is to check if it is possible to rearrange the array elements such that arr[2 * i + 1] = 2* arr[2 * i] for every ith index. If it is possible to do so, then print “Yes. Otherwise, print “No”.
Examples:
Input: arr[] = {4, -2, 2, -4}, N = 2
Output: Yes
Explanation: Rearrange the array as arr[] = {-2, -4, 2, 4}.Input: arr[] = {3, 1, 3, 6}, N = 2
Output: No
Approach: The idea to solve the given problem is to use a Map and the observation that one needs N distinct pairs such that one element is double that of another element. Follow the steps below to solve the problem:
- Initialize a map < integer, integer >, say, count, to store the count of array elements.
- Traverse the array arr[] and update the count of each element in the Map count.
- Iterate over the map count and perform the following operations:
- Initialize a variable, say want, to form a pair with the current element, say X, and assign want = X/2, if X is less than 0. Otherwise, assign want = 2*X.
- Check if X is less than 0 and X is odd or the count of X is greater than the count of want, then print “No” as it is impossible to form the pair of remaining X with any other element of the array.
- Otherwise, update the count of want in the Map count as count(want) – count(X).
- After completing the above steps, print “Yes” as there exists any combination of elements that satisfy the given property.
Below is the implementation of the above approach:
C++
// cpp program of the above approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible// to rearrange the array elements// that satisfies the given conditionsstring canReorderDoubled(vector<int> A){ // Stores the count of elements map<int,int> count; // Update the hash table for (int a : A) count[a]++; // Traverse the hash table for (auto x : count) { // If the count of current // element is zero if (x.second == 0) continue; // Stores the element needed // to form a pair with the // current element int xx = x.first; int want = xx < 0 ? xx / 2 : xx * 2; // If x is less than zero and odd if (xx < 0 && xx % 2 != 0) return "No"; // If count of x is greater // than count of want if (x.second > count[want]) return "No"; // Update the count of want // in the hash table count[want] -= x.second; } // Return true if none of the // above cases satisfies return "Yes";}// Driver Codeint main(){ vector<int> arr = { 4, -2, 2, -4 }; int N = 2; string res = canReorderDoubled(arr); // Print the result obtained cout<<(res);}// This code is contributed by mohit kumar 29. |
Java
// Java program of the above approachimport java.io.*;import java.util.*;class GFG { // Function to check if it is possible // to rearrange the array elements // that satisfies the given conditions public static String canReorderDoubled(int[] A) { // Stores the count of elements Map<Integer, Integer> count = new TreeMap<>(); // Update the hash table for (int a : A) count.put( a, count.getOrDefault(a, 0) + 1); // Traverse the hash table for (int x : count.keySet()) { // If the count of current // element is zero if (count.get(x) == 0) continue; // Stores the element needed // to form a pair with the // current element int want = x < 0 ? x / 2 : x * 2; // If x is less than zero and odd if (x < 0 && x % 2 != 0) return "No"; // If count of x is greater // than count of want if (count.get(x) > count.getOrDefault(want, 0)) return "No"; // Update the count of want // in the hash table count.put(want, count.get(want) - count.get(x)); } // Return true if none of the // above cases satisfies return "Yes"; } // Driver Code public static void main(String[] args) { int[] arr = { 4, -2, 2, -4 }; int N = 2; String res = canReorderDoubled(arr); // Print the result obtained System.out.println(res); }} |
Python3
# Python 3 program of the above approach# Function to check if it is possible# to rearrange the array elements# that satisfies the given conditionsdef canReorderDoubled(A): # Stores the count of elements count = {} # Update the hash table for a in A: if a in count: count[a] += 1 else: count[a] = 1 # Traverse the hash table for key,value in count.items(): # If the count of current # element is zero if (value == 0): continue # Stores the element needed # to form a pair with the # current element xx = key if xx < 0: want = xx / 2 else: want = xx * 2 # If x is less than zero and odd if (xx < 0 and xx % 2 != 0): return "No" # If count of x is greater # than count of want if (want in count and value > count[want]): return "No" # Update the count of want # in the hash table if want in count: count[want] -= value # Return true if none of the # above cases satisfies return "Yes"# Driver Codeif __name__ == '__main__': arr = [4, -2, 2, -4] N = 2 res = canReorderDoubled(arr) # Print the result obtained print(res) # This code is contributed by bgangwar59. |
C#
using System;using System.Collections.Generic;namespace ConsoleApp1{ class Program { // Function to check if it is possible // to rearrange the array elements // that satisfies the given conditions public static string CanReorderDoubled(int[] A) { // Stores the count of elements Dictionary<int, int> count = new Dictionary<int, int>(); // Update the hash table foreach (int a in A) { if (count.ContainsKey(a)) { count[a]++; } else { count[a] = 1; } } // Traverse the hash table foreach (int x in count.Keys) { // If the count of current // element is zero if (count[x] == 0) continue; // Stores the element needed // to form a pair with the // current element int want = x < 0 ? x / 2 : x * 2; // If x is less than zero and odd if (x < 0 && x % 2 != 0) return "No"; // If count of x is greater // than count of want if (count[x] > count.GetValueOrDefault(want, 0)) return "Yes"; // Update the count of want // in the hash table count[want] = count.GetValueOrDefault(want, 0) - count[x]; } // Return true if none of the // above cases satisfies return "Yes"; } static void Main(string[] args) { int[] arr = { 4, -2, 2, -4 }; string res = CanReorderDoubled(arr); // Print the result obtained Console.WriteLine(res); } }}// This code is contributed by aadityaburujwale. |
Javascript
<script>// Javascript program of the above approach// Function to check if it is possible// to rearrange the array elements// that satisfies the given conditionsfunction canReorderDoubled(A){ // Stores the count of elements var count= new Map(); // Update the hash table A.forEach(a => { if(count.has(a)) count.set(a, count.get(a)+1) else count.set(a, 1) }); // Traverse the hash table count.forEach((value, key) => { // If the count of current // element is zero if (value != 0) { // Stores the element needed // to form a pair with the // current element var xx = key; var want = xx < 0 ? xx / 2 : xx * 2; // If x is less than zero and odd if (xx < 0 && xx % 2 != 0) return "No"; // If count of x is greater // than count of want if (value > count.get(want)) return "No"; // Update the count of want // in the hash table if(count.has(want)) count.set(want, count.get(want)-value) } }); // Return true if none of the // above cases satisfies return "Yes";}// Driver Codevar arr = [4, -2, 2, -4];var N = 2;var res = canReorderDoubled(arr);// Print the result obtaineddocument.write(res);</script> |
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!
