Given an array arr[] of N positive integers (> 0). The task is to check if it is possible to make all array elements equal by performing the given operation. Print “Yes” if possible, else print “No“. The operation that can be performed is
- Choose two indices i, j, 1 < i, j < N, i and j are distinct.
- Replace a[i] with value a[i] divided by a[j] (ceil value).
Examples:
Input: N = 3, arr[] = {5, 1, 4}
Output: No
Explanation: There exists no sequence of operation which can make all elements equal to 1.Input: N = 4, arr[] = {3, 3, 4, 4}
Output: Yes
Explanation: We can perform the following operations,
- i = 3, j = 0, arr[3] = ceil(4/3) = 2, Array becomes { 3, 3, 4, 2}
- i = 2, j = 3, arr[2] = ceil(4/2) = 2, Array becomes { 3, 3, 2, 2}
- i = 1, j = 3, arr[1] = ceil(3/2) = 2, Array becomes { 3, 2, 2, 2}
- i = 0, j = 3, arr[0] = ceil(3/2) = 2, Array becomes { 2, 2, 2, 2}
Approach: This can be solved with the following idea:
- Observation 1. If all numbers are equal initially, we have to do nothing & the answer is “Yes“.
- Observation 2. If some ai is 1, then the answer is “No” because this ai can’t become bigger during operations and all other elements can’t become 1 because after the last operation some aj > 1.
- Observation 3. If all ai ≥ 2, then the answer is “Yes”. We can simulate an algorithm: let’s take i, such that ai is the maximum possible, and j, such that aj is the smallest possible. Make operation with (i, j). It is true, because after each operation ai decreases at least by times (and rounded up) and all elements are bounded ax ≥ 2 after each operation (ai >= aj and aj >= 2).
Below are the steps involved in the implementation of the code:
- Initialize allSame = true and isOne = false
- For i = 0 to N – 1,
- Set allSame = false if arr[i] != arr[0]
- Set isOne = True if arr[i] equals 1
[end for] - If allSame equals true, then print “Yes”
- else if, isOne equals true, then print “No”
- else print “Yes“
Below is the implementation for the above approach:
C++
// C++ code of the above approach:#include <bits/stdc++.h>using namespace std;// Function to check whether all elements// can become equal or notvoid equalizeDividing(int arr[], int n){ // Initialize the variables bool allSame = true, isOne = false; // Perform the algorithm for (int i = 0; i < n; i++) { if (arr[i] != arr[0]) { allSame = false; } if (arr[i] == 1) { isOne = true; } } if (allSame == true) { cout << "Yes" << endl; } else if (isOne == true) { cout << "No" << endl; } else { cout << "Yes" << endl; }}// Driver codeint main(){ int n1 = 3; int arr1[] = { 5, 1, 4 }; // Function call equalizeDividing(arr1, n1); int n2 = 4; int arr2[] = { 3, 3, 4, 4 }; // Function call equalizeDividing(arr2, n2); int n3 = 4; int arr3[] = { 1, 1, 1, 1 }; // Function call equalizeDividing(arr3, n3); return 0;} |
Java
// java code of the above approach:import java.util.Arrays;class GFG { // Function to check whether all elements // can become equal or not static void equalizeDividing(int[] arr, int n) { // Initialize the variables boolean allSame = true, isOne = false; // Perform the algorithm for (int i = 0; i < n; i++) { if (arr[i] != arr[0]) { allSame = false; } if (arr[i] == 1) { isOne = true; } } if (allSame) { System.out.println("Yes"); } else if (isOne) { System.out.println("No"); } else { System.out.println("Yes"); } } // Driver code public static void main(String[] args) { int n1 = 3; int[] arr1 = { 5, 1, 4 }; // Function call equalizeDividing(arr1, n1); int n2 = 4; int[] arr2 = { 3, 3, 4, 4 }; // Function call equalizeDividing(arr2, n2); int n3 = 4; int[] arr3 = { 1, 1, 1, 1 }; // Function call equalizeDividing(arr3, n3); }}// This code is contributed by shivamgupta0987654321 |
Python3
# Python3 code of the above approach:# Function to check whether all elements# can become equal or notdef equalizeDividing(arr, n): # Initialize the variables allSame = True isOne = False # Perform the algorithm for i in range(n): if arr[i] != arr[0]: allSame = False if arr[i] == 1: isOne = True if allSame: print("Yes") elif isOne: print("No") else: print("Yes")# Driver codeif __name__ == "__main__": n1 = 3 arr1 = [5, 1, 4] # Function call equalizeDividing(arr1, n1) n2 = 4 arr2 = [3, 3, 4, 4] # Function call equalizeDividing(arr2, n2) n3 = 4 arr3 = [1, 1, 1, 1] # Function call equalizeDividing(arr3, n3)# This code is contributed by rambabuguphka |
C#
// c# code of the above approach:using System;class GFG { // Function to check whether all elements // can become equal or not static void equalizeDividing(int[] arr, int n) { // Initialize the variables bool allSame = true, isOne = false; // Perform the algorithm for (int i = 0; i < n; i++) { if (arr[i] != arr[0]) { allSame = false; } if (arr[i] == 1) { isOne = true; } } if (allSame) { Console.WriteLine("Yes"); } else if (isOne) { Console.WriteLine("No"); } else { Console.WriteLine("Yes"); } } // Driver code public static void Main(string[] args) { int n1 = 3; int[] arr1 = { 5, 1, 4 }; // Function call equalizeDividing(arr1, n1); int n2 = 4; int[] arr2 = { 3, 3, 4, 4 }; // Function call equalizeDividing(arr2, n2); int n3 = 4; int[] arr3 = { 1, 1, 1, 1 }; // Function call equalizeDividing(arr3, n3); }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// JavaScript code of the above approach:// Function to check whether all elements// can become equal or notfunction equalizeDividing(arr, n) { // Initialize the variables let allSame = true; let isOne = false; // Perform the algorithm for (let i = 0; i < n; i++) { if (arr[i] !== arr[0]) { allSame = false; } if (arr[i] === 1) { isOne = true; } } if (allSame) { console.log("Yes"); } else if (isOne) { console.log("No"); } else { console.log("Yes"); }}// Driver codelet n1 = 3;let arr1 = [5, 1, 4];// Function callequalizeDividing(arr1, n1);let n2 = 4;let arr2 = [3, 3, 4, 4];// Function callequalizeDividing(arr2, n2);let n3 = 4;let arr3 = [1, 1, 1, 1];// Function callequalizeDividing(arr3, n3);// This code is contributed by Tapesh(tapeshdua420) |
Output
No Yes Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
Share your thoughts in the comments
