Given an array arr[] of n integers and an integer k. The task is to make all the elements of arr[] equal with the given operation. In a single operation, any non-negative number x ? k (can be a floating point value) can be added to any element of the array and k will be updated as k = k – x. Print Yes is possible else print No.
Examples:Â
Input: k = 8, arr[] = {1, 2, 3, 4}Â
Output: YesÂ
1 + 3.5 = 4.5Â
2 + 2.5 = 4.5Â
3 + 1.5 = 4.5Â
4 + 0.5 = 4.5Â
3.5 + 2.5 + 1.5 + 0.5 = 8 = kInput: k = 2, arr[] = {1, 2, 3, 4}Â
Output: -1Â
Approach: Since the task is to make all elements of the array equal and the total of additions has to be exactly k. There is only a single value at which we can make them all of these elements equal i.e. (sum(arr) + k) / n. If there is an element in the array which is already greater than this value then the answer does not exist otherwise print Yes.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;Â
// Function that returns true if all the elements// of the array can be made equal// with the given operationbool isPossible(int n, int k, int arr[]){Â
    // To store the sum of the array elements    // and the maximum element from the array    int sum = arr[0], maxVal = arr[0];Â
    for (int i = 1; i < n; i++) {        sum += arr[i];        maxVal = max(maxVal, arr[i]);    }Â
    if ((float)maxVal > (float)(sum + k) / n)        return false;Â
    return true;}Â
// Driver codeint main(){Â Â Â Â int k = 8;Â Â Â Â int arr[] = { 1, 2, 3, 4 };Â Â Â Â int n = sizeof(arr) / sizeof(arr[0]);Â
    if (isPossible(n, k, arr))        cout << "Yes";    else        cout << "No";Â
    return 0;} |
Java
//Java implementation of the approachimport java.io.*;Â
class GFG {Â Â Â Â Â // Function that returns true if all // the elements of the array can be // made equal with the given operationstatic boolean isPossible(int n, int k, int arr[]){Â
    // To store the sum of the array elements    // and the maximum element from the array    int sum = arr[0];    int maxVal = arr[0];Â
    for (int i = 1; i < n; i++)     {        sum += arr[i];        maxVal = Math.max(maxVal, arr[i]);    }Â
    if ((float)maxVal > (float)(sum + k) / n)        return false;Â
    return true;}Â
    // Driver code    public static void main (String[] args)     {             int k = 8;        int arr[] = { 1, 2, 3, 4 };        int n = arr.length;Â
        if (isPossible(n, k, arr))            System.out.println ("Yes");        else            System.out.println( "No");    }}Â
// This code is contributed by @Tushil. |
Python3
# Python 3 implementation of the approachÂ
# Function that returns true if all # the elements of the array can be # made equal with the given operationdef isPossible(n, k, arr):         # To store the sum of the array elements    # and the maximum element from the array    sum = arr[0]    maxVal = arr[0];Â
    for i in range(1, n):        sum += arr[i]        maxVal = max(maxVal, arr[i])Â
Â
    if (int(maxVal)> int((sum + k) / n)):        return FalseÂ
    return TrueÂ
# Driver codeif __name__ == '__main__':Â Â Â Â k = 8Â Â Â Â arr = [1, 2, 3, 4]Â Â Â Â n = len(arr)Â
    if (isPossible(n, k, arr)):        print("Yes")    else:        print("No")Â
Â
# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approach using System;Â
class GFG {          // Function that returns true if all     // the elements of the array can be     // made equal with the given operation     static bool isPossible(int n,                         int k, int []arr)     {              // To store the sum of the array elements         // and the maximum element from the array         int sum = arr[0];         int maxVal = arr[0];                  for (int i = 1; i < n; i++)         {             sum += arr[i];             maxVal = Math.Max(maxVal, arr[i]);         }              if ((float)maxVal > (float)(sum + k) / n)             return false;              return true;     }          // Driver code     public static void Main()     {                  int k = 8;         int []arr = { 1, 2, 3, 4 };         int n = arr.Length;              if (isPossible(n, k, arr))             Console.WriteLine("Yes");         else            Console.WriteLine( "No");     } } Â
// This code is contributed by Ryuga |
PHP
<?php// PHP implementation of the approach// Function that returns true if // all the elements of the array // can be made equal with the given operationÂ
function isPossible($n, $k, $arr){Â
    // To store the sum of the array elements    // and the maximum element from the array    $sum = $arr[0];    $maxVal = $arr[0];Â
    for ($i = 1; $i < $n; $i++)     {        $sum += $arr[$i];        $maxVal = max($maxVal, $arr[$i]);    }Â
    if ((float)$maxVal > (float)($sum + $k) / $n)        return false;Â
    return true;}Â
    // Driver code    $k = 8;    $arr = array( 1, 2, 3, 4 );    $n = sizeof($arr) / sizeof($arr[0]);Â
    if (isPossible($n, $k, $arr))        echo "Yes";    else        echo "No";Â
# This code is contributed by akt_miit.?> |
Javascript
<script>Â
// Javascript implementation of the above approachÂ
// Function that returns true if all // the elements of the array can be // made equal with the given operationfunction isPossible(n, k, arr){Â
    // To store the sum of the array elements    // and the maximum element from the array    let sum = arr[0];    let maxVal = arr[0];Â
    for (let i = 1; i < n; i++)     {        sum += arr[i];        maxVal = Math.max(maxVal, arr[i]);    }Â
    if (maxVal > (sum + k) / n)        return false;Â
    return true;}Â
// driver program             let k = 8;        let arr = [ 1, 2, 3, 4 ];        let n = arr.length;Â
        if (isPossible(n, k, arr))            document.write ("Yes");        else            document.write( "No");   </script> |
Output
Yes
Complexity Analysis:
- 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!
