Check if all array elements can be made divisible by K by replacing array elements with sum of pairs
Given an array arr[] of size N and a positive integer K, the task is to make every element of the array divisible by K by repeatedly selecting a pair of indices (i, j) and perform arr[i] = arr[i] + arr[j].
Examples:
Input: arr[] = {3, 6, 3}, K = 6
Output: True
Explanation:
Update arr[0] = arr[0] + arr[0].
Update arr[2] = arr[2] + arr[2]Input: arr[] = {6, 6, 8, 7, 3}, K = 6
Output: False
Approach: Follow the steps below to solve the problem:
- Traverse the array arr[]:
- Check if arr[i] is divisible by K or not:
- Initialize a variable, say temp, to store the value of arr[i] after each iteration.
- Repeatedly Multiply arr[i] by 2 until arr[i] < K * temp.
- Check if arr[i] % K != 0. If found to be true, print False and return.
- Check if arr[i] is divisible by K or not:
- After completing the above steps, print True as all the elements are now divisible by K.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach #include <bits/stdc++.h> using namespace std; // Utility function to check if all array // elements can be made divisible by K or not bool makeArrayDivisibleByKUtil( int arr[], int N, int K) { // Traverse the array for ( int i = 0; i < N; i++) { // Check whether arr[i] is // divisible by K or not if (arr[i] % K != 0) { // Stores value of arr[i] int temp = arr[i]; while (arr[i] < K * temp) { // Multiply by 2 until it // is less than K * temp arr[i] = arr[i] * 2; } if (arr[i] % K != 0) { return false ; } } } // Return true as all array // elements are divisible by K return true ; } // Function to check whether all array // elements can be made divisible by K or not void makeArrayDivisibleByK( int arr[], int N, int K) { if (makeArrayDivisibleByKUtil(arr, N, K)) { cout << "True" << endl; } else { cout << "False" << endl; } } // Driver Code int main() { // Given array int arr[] = { 3, 6, 3 }; // Size of the array int N = sizeof (arr) / sizeof (arr[0]); // Given value of K int K = 6; makeArrayDivisibleByK(arr, N, K); return 0; } |
C
#include<stdio.h> // Utility function to check if all array // elements can be made divisible by K or not int makeArrayDivisibleByKUtil( int arr[], int N, int K) { // Traverse the array for ( int i = 0; i < N; i++) { // Check whether arr[i] is // divisible by K or not if (arr[i] % K != 0) { // Stores value of arr[i] int temp = arr[i]; while (arr[i] < K * temp) { // Multiply by 2 until it // is less than K * temp arr[i] = arr[i] * 2; } if (arr[i] % K != 0) { return 0; } } } // Return true as all array // elements are divisible by K return 1; } // Function to check whether all array // elements can be made divisible by K or not void makeArrayDivisibleByK( int arr[], int N, int K) { if (makeArrayDivisibleByKUtil(arr, N, K)) { printf ( "True\n" ); } else { printf ( "False\n" ); } } // Driver Code int main() { // Given array int arr[] = { 3,6,3 }; // Size of the array int N = sizeof (arr) / sizeof (arr[0]); // Given value of K int K = 6; makeArrayDivisibleByK(arr, N, K); return 0; } // This code is contributed by santoshcharan. |
Java
import java.io.*; class GFG { public static boolean makeArrayDivisibleBykUtil( int arr[], int n, int k) { // Traverse the array for ( int i = 0 ; i < n; i++) { // Check whether arr[i] is // divisible by k or not if (arr[i] % k != 0 ) { // Stores value of arr[i] int temp = arr[i]; while (arr[i] < k * arr[i]) { // Multiply by 2 until it // is less than k*temp arr[i] = arr[i] * 2 ; } if (arr[i] % k != 0 ) { return false ; } } } // Return true as all array // elements are divisible by k return true ; } public static void makeArrayDivisibleByk( int arr[], int n, int k) { if (makeArrayDivisibleBykUtil(arr, n, k)) { System.out.println( "True" ); } else { System.out.println( "False" ); } } // Driver Code public static void main(String[] args) { // Given array int [] arr = { 3 , 6 , 3 }; // Size of the array int n = 3 ; int k = 6 ; // Calling the function makeArrayDivisibleByk(arr, n, k); } } // This code is contributed by santoshcharan. |
Python3
# Python 3 Program for the above approach # Utility function to check if all array # elements can be made divisible by K or not def makeArrayDivisibleByKUtil(arr, N, K): # Traverse the array for i in range (N): # Check whether arr[i] is # divisible by K or not if (arr[i] % K ! = 0 ): # Stores value of arr[i] temp = arr[i] while (arr[i] < K * temp): # Multiply by 2 until it # is less than K * temp arr[i] = arr[i] * 2 if (arr[i] % K ! = 0 ): return False # Return true as all array # elements are divisible by K return True # Function to check whether all array # elements can be made divisible by K or not def makeArrayDivisibleByK(arr, N, K): if (makeArrayDivisibleByKUtil(arr, N, K)): print ( "True" ) else : print ( "False" ) # Driver Code if __name__ = = '__main__' : # Given array arr = [ 3 , 6 , 3 ] # Size of the array N = len (arr) # Given value of K K = 6 makeArrayDivisibleByK(arr, N, K) # This code is contributed by bgangwar59. |
C#
using System; class GFG { public static bool makeArrayDivisibleBykUtil( int [] arr, int n, int k) { // Traverse the array for ( int i = 0; i < n; i++) { // Check whether arr[i] is // divisible by k or not if (arr[i] % k != 0) { // Stores value of arr[i] //int temp = arr[i]; while (arr[i] < k * arr[i]) { // Multiply by 2 until it // is less than k*temp arr[i] = arr[i] * 2; } if (arr[i] % k != 0) { return false ; } } } // Return true as all array // elements are divisible by k return true ; } public static void makeArrayDivisibleByk( int []arr, int n, int k) { if (makeArrayDivisibleBykUtil(arr, n, k)) { Console.WriteLine( "True" ); } else { Console.WriteLine( "False" ); } } // Driver Code public static void Main( string [] args) { // Given array int [] arr = { 3 , 6 , 3}; // Size of the array int n = 3; int k = 6; // Calling the function makeArrayDivisibleByk(arr, n, k); } } // This code is contributed by chitranayal. |
Javascript
<script> // Javascript Program for the above approach // Utility function to check if all array // elements can be made divisible by K or not function makeArrayDivisibleByKUtil(arr, N, K) { // Traverse the array for (let i = 0; i < N; i++) { // Check whether arr[i] is // divisible by K or not if (arr[i] % K != 0) { // Stores value of arr[i] let temp = arr[i]; while (arr[i] < K * temp) { // Multiply by 2 until it // is less than K * temp arr[i] = arr[i] * 2; } if (arr[i] % K != 0) { return false ; } } } // Return true as all array // elements are divisible by K return true ; } // Function to check whether all array // elements can be made divisible by K or not function makeArrayDivisibleByK(arr, N, K) { if (makeArrayDivisibleByKUtil(arr, N, K)) { document.write( "True<br>" ); } else { document.write( "False<br>" ); } } // Driver Code // Given array let arr = [ 3, 6, 3 ]; // Size of the array let N = arr.length; // Given value of K let K = 6; makeArrayDivisibleByK(arr, N, K); // This code is contributed by rishavmahato348 </script> |
Output:
True
Time Complexity: O(N * logN)
Auxiliary Space: O(1)