Wednesday, October 9, 2024
Google search engine
HomeData Modelling & AIEqualize all Array elements by dividing with another Array element

Equalize all Array elements by dividing with another Array element

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 not
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 == true) {
        cout << "Yes" << endl;
    }
    else if (isOne == true) {
        cout << "No" << endl;
    }
    else {
        cout << "Yes" << endl;
    }
}
 
// Driver code
int 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 not
 
 
def 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 code
if __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 not
 
function 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 code
let n1 = 3;
let arr1 = [5, 1, 4];
 
// Function call
equalizeDividing(arr1, n1);
 
let n2 = 4;
let arr2 = [3, 3, 4, 4];
 
// Function call
equalizeDividing(arr2, n2);
 
let n3 = 4;
let arr3 = [1, 1, 1, 1];
 
// Function call
equalizeDividing(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!

Commit to GfG’s Three-90 Challenge! Purchase a course, complete 90% in 90 days, and save 90% cost click here to explore.

Last Updated :
17 Aug, 2023
Like Article
Save Article


Previous

<!–

8 Min Read | Java

–>


Next


<!–

8 Min Read | Java

–>

Share your thoughts in the comments

RELATED ARTICLES

Most Popular

Recent Comments