Given an array arr of length N and two integers K and X. For every element arri in the array, if arri > 0 then the elements which are adjacent to it and the element itself will get incremented by 2 for all 1≤i≤N. Check if the sum of all array elements after performing the K operation is equal to X or not.
Examples:
Input: arr[] = { 0, 0, 1, 0, 0, 3 }, K = 2, X = 36
Output: True
Explanation: Initially arr[ ] = { 0, 0, 1, 0, 0, 3 }
After one operation array will be arr [ ] = { 0, 2, 3, 4, 4, 5 }
after Second times array will be arr [ ] = { 2, 4, 7, 8, 8, 7 }
Thus, sum of array is 36 which is equal to XInput: arr[ ] = {10, 6, 12, 8, 10, 8}, K = 2, X = 25
Output: False
Approach: This problem can be solved using brute force hit and trial technique:
- Traverse the given array
- For every index, increment the value at that index and its adjacent index by 2, except for the first and last element because they have only one element adjacent to them.
- Repeat the operations for every possibility in given array till array sum becomes at most X
- If after K operations, in any possibility, the array sum becomes X, return true.
- Else return false, if no such possibility exists.
Below is the implementation of the above approach:
C++
// C++ program to check whether sum// Is equal to target value// After K operations#include <bits/stdc++.h>using namespace std;// Function to check sum of array// Value is equal to Targetbool find(int arr[], int N, int K, int Target){ while (K--) { for (int i = 0; i < N; i++) { // If it is first element just increment // next element if (arr[i] > 0 && i == 0) { arr[i + 1] = arr[i + 1] + 2; } // If it is last element just increment // Last second element else if (arr[i] > 0 && i == N - 1) { arr[N - 2] = arr[N - 2] + 2; } // If it is not a first element // Or not a last element // Increment both adjacent value by 2 else if (arr[i] > 0) { arr[i - 1] = arr[i - 1] + 2; arr[i + 1] = arr[i + 1] + 2; } } } // Calculate sum after performing // k times operation int ans = accumulate(arr, arr + N, 0); if (ans == Target) { return 1; } else { return 0; }}// Driver Codeint main(){ int arr[] = { 0, 0, 1, 0, 0, 3 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 2; int Target = 36; // function call cout << (find(arr, N, K, Target) ? "true" : "false"); return 0;} |
Java
// JAVA program to check whether sum// Is equal to target value// After K operationsimport java.util.*;class GFG{ // Function to check sum of array // Value is equal to Target public static boolean find(int arr[], int N, int K, int Target) { while ((K--) != 0) { for (int i = 0; i < N; i++) { // If it is first element just increment // next element if (arr[i] > 0 && i == 0) { arr[i + 1] = arr[i + 1] + 2; } // If it is last element just increment // Last second element else if (arr[i] > 0 && i == N - 1) { arr[N - 2] = arr[N - 2] + 2; } // If it is not a first element // Or not a last element // Increment both adjacent value by 2 else if (arr[i] > 0) { arr[i - 1] = arr[i - 1] + 2; arr[i + 1] = arr[i + 1] + 2; } } } // Calculate sum after performing // k times operation int ans = 0; for (int i = 0; i < arr.length; i++) { ans += arr[i]; } if (ans == Target) { return true; } else { return false; } } // Driver Code public static void main(String[] args) { int arr[] = new int[] { 0, 0, 1, 0, 0, 3 }; int N = arr.length; int K = 2; int Target = 36; // function call System.out.print( (find(arr, N, K, Target) ? "true" : "false")); }}// This code is contributed by Taranpreet |
Python3
# Function to check sum of array# Value is equal to Targetdef find(arr, N, K, Target) : for j in range(K, 1, -1): for i in range(0, N): # If it is first element just increment # next element if (arr[i] > 0 and i == 0) : arr[i + 1] = arr[i + 1] + 2 # If it is last element just increment # Last second element elif (arr[i] > 0 and i == N - 1) : arr[N - 2] = arr[N - 2] + 2 # If it is not a first element # Or not a last element # Increment both adjacent value by 2 elif (arr[i] > 0) : arr[i - 1] = arr[i - 1] + 2 arr[i + 1] = arr[i + 1] + 2 # Calculate sum after performing # k times operation ans = 0 for i in range(0, len(arr)): ans += arr[i] if (ans == Target) : return 1 else : return 0 # Driver Codearr = [ 0, 0, 1, 0, 0, 3 ] N = len(arr)K = 2Target = 36# function callprint ( "false" if find(arr, N, K, Target) else "true" )# This code is contributed by sanjoy_62. |
C#
// C# program to check whether sum// Is equal to target value// After K operationsusing System;public class GFG{ // Function to check sum of array // Value is equal to Target static bool find(int[] arr, int N, int K, int Target) { while ((K--) != 0) { for (int i = 0; i < N; i++) { // If it is first element just increment // next element if (arr[i] > 0 && i == 0) { arr[i + 1] = arr[i + 1] + 2; } // If it is last element just increment // Last second element else if (arr[i] > 0 && i == N - 1) { arr[N - 2] = arr[N - 2] + 2; } // If it is not a first element // Or not a last element // Increment both adjacent value by 2 else if (arr[i] > 0) { arr[i - 1] = arr[i - 1] + 2; arr[i + 1] = arr[i + 1] + 2; } } } // Calculate sum after performing // k times operation int ans = 0; for (int i = 0; i < arr.Length; i++) { ans += arr[i]; } if (ans == Target) { return true; } else { return false; } } // Driver Code static public void Main (){ int[] arr = { 0, 0, 1, 0, 0, 3 }; int N = arr.Length; int K = 2; int Target = 36; // function call Console.Write( (find(arr, N, K, Target) ? "true" : "false")); }}// This code is contributed by hrithikgarg03188. |
Javascript
<script> // JavaScript program to check whether sum // Is equal to target value // After K operations // Function to check sum of array // Value is equal to Target const find = (arr, N, K, Target) => { while (K--) { for (let i = 0; i < N; i++) { // If it is first element just increment // next element if (arr[i] > 0 && i == 0) { arr[i + 1] = arr[i + 1] + 2; } // If it is last element just increment // Last second element else if (arr[i] > 0 && i == N - 1) { arr[N - 2] = arr[N - 2] + 2; } // If it is not a first element // Or not a last element // Increment both adjacent value by 2 else if (arr[i] > 0) { arr[i - 1] = arr[i - 1] + 2; arr[i + 1] = arr[i + 1] + 2; } } } // Calculate sum after performing // k times operation let ans = 0; for (let indx in arr) { ans += arr[indx]; } // accumulate(arr, arr + N, 0); if (ans == Target) { return 1; } else { return 0; } } // Driver Code let arr = [0, 0, 1, 0, 0, 3]; let N = arr.length; let K = 2; let Target = 36; // function call (find(arr, N, K, Target) ? document.write("true") : document.write("false"));// This code is contributed by rakeshsahni</script> |
Output
true
Time Complexity: O(N * K)
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!
