Find the array element having maximum frequency of the digit K
Given an array arr[] of size N and an integer K, the task is to find an array element that contains the digit K a maximum number of times. If more than one solutions exist, then print any one of them. Otherwise, print -1.
Examples:
Input: arr[] = {3, 77, 343, 456}, K = 3
Output: 343
Explanation:
Frequency of 3 in array elements: 1, 0, 2, 0
343 has maximum frequency i.e. 2.Input: arr[] = {1, 1111, 111, 11}, K = 1
Output: 1111
Explanation:
Frequency of 1 in array elements: 1, 4, 3, 2
1111 has maximum frequency i.e. 4.
Approach: The idea is to traverse the array and for every individual array element, count the occurrences of the digit K in it. Follow the steps below to solve the problem:
- Initialize the max frequency of digit K, say maxfreq, as 0.
- Traverse the given array from the start element till the end.
- For every traversed element, find the frequency of digit K in that element. If it is greater than maxfreq, then update maxfreq and store that element.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the count of // digits, k in the given number n int countFreq( int N, int K) { // Stores count of occurrence // of digit K in N int count = 0; // Iterate over digits of N while (N > 0) { // If current digit is k if (N % 10 == K) { // Update count count++; } // Update N N = N / 10; } return count; } // Utility function to find an array element // having maximum frequency of digit k int findElementUtil( int arr[], int N, int K) { // Stores frequency of // digit K in arr[i] int c = 0; // Stores maximum frequency of // digit K in the array int max = 0; // Stores an array element having // maximum frequency of digit k int ele; // Initialize max max = 0; // Traverse the array for ( int i = 0; i < N; i++) { // Count the frequency of // digit k in arr[i] c = countFreq(arr[i], K); // Update max with maximum // frequency found so far if (c > max) { max = c; // Update ele ele = arr[i]; } } // If there is no array element // having digit k in it if (max == 0) return -1; else return ele; } // Function to find an array element // having maximum frequency of digit k void findElement( int arr[], int K, int N) { // Stores an array element having // maximum frequency of digit k int ele = findElementUtil(arr, N, K); // If there is no element found // having digit k in it if (ele == -1) cout << "-1" ; else // Print the element having max // frequency of digit k cout << ele; } // Driver Code int main() { // The digit whose max // occurrence has to be found int K = 1; // Given array int arr[] = { 1, 1111, 111, 11}; // Size of array int N = sizeof (arr) / sizeof (arr[0]); // Function Call findElement(arr, K, N); return 0; } |
Java
// Java program for the above approach public class GFG { // Function to find the count of // digits, k in the given number n static int countFreq( int N, int K) { // Stores count of occurrence // of digit K in N int count = 0 ; // Iterate over digits of N while (N > 0 ) { // If current digit is k if (N % 10 == K) { // Update count count++; } // Update N N = N / 10 ; } return count; } // Utility function to find an array element // having maximum frequency of digit k static int findElementUtil( int arr[], int N, int K) { // Stores frequency of // digit K in arr[i] int c; // Stores maximum frequency of // digit K in the array int max; // Stores an array element having // maximum frequency of digit k int ele = 0 ; // Initialize max max = 0 ; // Traverse the array for ( int i = 0 ; i < N; i++) { // Count the frequency of // digit k in arr[i] c = countFreq(arr[i], K); // Update max with maximum // frequency found so far if (c > max) { max = c; // Update ele ele = arr[i]; } } // If there is no array element // having digit k in it if (max == 0 ) return - 1 ; else return ele; } // Function to find an array element // having maximum frequency of digit k static void findElement( int arr[], int N, int K) { // Stores an array element having // maximum frequency of digit k int ele = findElementUtil(arr, N, K); // If there is no element found // having digit k in it if (ele == - 1 ) System.out.print( "-1" ); else // Print the element having max // frequency of digit k System.out.print(ele); } // Driver Code public static void main (String[] args) { // The digit whose max // occurrence has to be found int K = 1 ; // Given array int arr[] = { 1 , 1111 , 111 , 11 }; // Size of array int N = arr.length; // Function Call findElement(arr, N, K); } }; // This code is contributed by AnkThon |
Python3
# Python3 program for the above approach # Function to find the count of # digits, k in the given number n def countFreq(N, K): # Stores count of occurrence # of digit K in N count = 0 # Iterate over digits of N while (N > 0 ): # If current digit is k if (N % 10 = = K): # Update count count + = 1 # Update N N = N / / 10 return count # Utility function to find an array element # having maximum frequency of digit k def findElementUtil(arr, N, K): # Stores frequency of # digit K in arr[i] c = 0 # Stores maximum frequency of # digit K in the array max = 0 # Stores an array element having # maximum frequency of digit k ele = 0 # Initialize max # max = 0 # Traverse the array for i in range (N): # Count the frequency of # digit k in arr[i] c = countFreq(arr[i], K) # Update max with maximum # frequency found so far if (c > max ): max = c # Update ele ele = arr[i] # If there is no array element # having digit k in it if ( max = = 0 ): return - 1 else : return ele # Function to find an array element # having maximum frequency of digit k def findElement(arr, N, K): # Stores an array element having # maximum frequency of digit k ele = findElementUtil(arr, N, K) # If there is no element found # having digit k in it if (ele = = - 1 ): print ( "-1" , end = "") else : # Print element having max # frequency of digit k print (ele) # Driver Code if __name__ = = '__main__' : # The digit whose max # occurrence has to be found K = 1 # Given array arr = [ 1 , 1111 , 111 , 11 ] # Size of array N = len (arr) # Function Call findElement(arr, N, K) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG { // Function to find the count of // digits, k in the given number n static int countFreq( int N, int K) { // Stores count of occurrence // of digit K in N int count = 0; // Iterate over digits of N while (N > 0) { // If current digit is k if (N % 10 == K) { // Update count count++; } // Update N N = N / 10; } return count; } // Utility function to find an array element // having maximum frequency of digit k static int findElementUtil( int []arr, int N, int K) { // Stores frequency of // digit K in arr[i] int c; // Stores maximum frequency of // digit K in the array int max; // Stores an array element having // maximum frequency of digit k int ele = 0; // Initialize max max = 0; // Traverse the array for ( int i = 0; i < N; i++) { // Count the frequency of // digit k in arr[i] c = countFreq(arr[i], K); // Update max with maximum // frequency found so far if (c > max) { max = c; // Update ele ele = arr[i]; } } // If there is no array element // having digit k in it if (max == 0) return -1; else return ele; } // Function to find an array element // having maximum frequency of digit k static void findElement( int []arr, int N, int K) { // Stores an array element having // maximum frequency of digit k int ele = findElementUtil(arr, N, K); // If there is no element found // having digit k in it if (ele == -1) Console.Write( "-1" ); else // Print the element having max // frequency of digit k Console.Write(ele); } // Driver Code public static void Main(String[] args) { // The digit whose max // occurrence has to be found int K = 1; // Given array int []arr = { 1, 1111, 111, 11}; // Size of array int N = arr.Length; // Function Call findElement(arr, N, K); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to implement // the above approach // Function to find the count of // digits, k in the given number n function countFreq(N, K) { // Stores count of occurrence // of digit K in N let count = 0; // Iterate over digits of N while (N > 0) { // If current digit is k if (N % 10 == K) { // Update count count++; } // Update N N = Math.floor(N / 10); } return count; } // Utility function to find an array element // having maximum frequency of digit k function findElementUtil(arr, N, K) { // Stores frequency of // digit K in arr[i] let c; // Stores maximum frequency of // digit K in the array let max; // Stores an array element having // maximum frequency of digit k let ele = 0; // Initialize max max = 0; // Traverse the array for (let i = 0; i < N; i++) { // Count the frequency of // digit k in arr[i] c = countFreq(arr[i], K); // Update max with maximum // frequency found so far if (c > max) { max = c; // Update ele ele = arr[i]; } } // If there is no array element // having digit k in it if (max == 0) return -1; else return ele; } // Function to find an array element // having maximum frequency of digit k function findElement(arr, N, K) { // Stores an array element having // maximum frequency of digit k let ele = findElementUtil(arr, N, K); // If there is no element found // having digit k in it if (ele == -1) document.write( "-1" ); else // Print the element having max // frequency of digit k document.write(ele); } // Driver Code // The digit whose max // occurrence has to be found let K = 3; // Given array let arr = [1, 1111, 111, 11]; // Size of array let N = arr.length; // Function Call findElement(arr, N, K}; // This code is contributed by souravghosh0416. </script> |
1111
Time Complexity: O(N * log10(N))
Auxiliary Space: O(1)
Another Approach:
- Start with an array arr[] of size N and an integer K.
- Initialize max_freq as 0 and result as -1.
- Traverse the array from the start to the end.
- For each element, count the number of occurrences of the digit K by iterating over its digits. You can do this by repeatedly dividing the number by 10 and checking the remainder for equality with K. If it’s equal, increment a frequency counter.
- Compare the frequency counter with max_freq. If it’s greater than max_freq, update max_freq with the frequency counter and result with the current element.
- After the traversal, if the max_freq is still 0, it means that no element contains the digit K, so return -1. Otherwise, return the result.
- Done.
C++
#include <iostream> #include <vector> using namespace std; int findElement( int arr[], int N, int K) { int max_freq = 0; int result = -1; for ( int i = 0; i < N; i++) { int num = arr[i]; int freq = 0; while (num > 0) { if (num % 10 == K) { freq++; } num /= 10; } if (freq > max_freq) { max_freq = freq; result = arr[i]; } } return result; } int main() { int arr[] = { 1, 1111, 111, 11 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 1; int result = findElement(arr, N, K); if (result == -1) { cout << "No element contains the digit " << K << endl; } else { cout<<result<<endl; } return 0; } |
Java
import java.util.Scanner; public class Main { // Function to find the element with the highest frequency of the digit K static int findElement( int [] arr, int N, int K) { int maxFreq = 0 ; int result = - 1 ; // Traverse the array and find the frequency of digit K in each element for ( int i = 0 ; i < N; i++) { int num = arr[i]; int freq = 0 ; while (num > 0 ) { if (num % 10 == K) { freq++; } num /= 10 ; } // Update the result if the current element has a higher frequency of digit K if (freq > maxFreq) { maxFreq = freq; result = arr[i]; } } return result; } // Driver Code public static void main(String[] args) { Scanner sc = new Scanner(System.in); int arr[] = { 1 , 1111 , 111 , 11 }; int N = arr.length; int K = 1 ; int result = findElement(arr, N, K); System.out.println(result); } } |
Python3
# Define a function to find the element with the highest frequency of a given digit def findElement(arr, N, K): max_freq = 0 result = - 1 for i in range (N): num = arr[i] freq = 0 # Count the frequency of the digit in the current number while num > 0 : if num % 10 = = K: freq + = 1 num / / = 10 # Update the result if the current number has a higher frequency of the digit if freq > max_freq: max_freq = freq result = arr[i] return result # Test the function with sample inputs arr = [ 1 , 1111 , 111 , 11 ] N = len (arr) K = 1 result = findElement(arr, N, K) if result = = - 1 : print ( "No element contains the digit" , K) else : print (result) |
C#
using System; namespace FindElementWithMaxDigit { class Program { // Function to find the element with the highest frequency of the digit K static int FindElement( int [] arr, int N, int K) { int maxFreq = 0; int result = -1; // Traverse the array and find the frequency of digit K in each element for ( int i = 0; i < N; i++) { int num = arr[i]; int freq = 0; while (num > 0) { if (num % 10 == K) { freq++; } num /= 10; } // Update the result if the current // element has a higher frequency of digit K if (freq > maxFreq) { maxFreq = freq; result = arr[i]; } } return result; } static void Main( string [] args) { int [] arr = { 1, 1111, 111, 11 }; int N = arr.Length; int K = 1; int result = FindElement(arr, N, K); if (result == -1) { Console.WriteLine($ "No element contains the digit {K}" ); } else { Console.WriteLine(result); } } } } |
Javascript
// Define a function to find the element with the highest frequency of a given digit function findElement(arr, N, K) { let max_freq = 0; let result = -1; for (let i = 0; i < N; i++) { let num = arr[i]; let freq = 0; // Count the frequency of the digit in the current number while (num > 0) { if (num % 10 == K) { freq += 1; } num = Math.floor(num / 10); } // Update the result if the current number has a higher frequency of the digit if (freq > max_freq) { max_freq = freq; result = arr[i]; } } return result; } // Test the function with sample inputs let arr = [1, 1111, 111, 11]; let N = arr.length; let K = 1; let result = findElement(arr, N, K); if (result == -1) { console.log( "No element contains the digit" , K); } else { console.log(result); } |
1111
Time Complexity: O(N*M)
Auxiliary Space: O(1)