Find Numbers with Even Number of Digits Leetcode Solution

Difficulty Level Easy
Frequently asked in Quora
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutionsViews 9307

In this problem, we are given an array of positive integers. We need to find the count of numbers with an even number of digits.

Example

Array = {123 , 34 , 3434 , 121 , 100}
2

Explanation: Only 34 and 3434 are integers with an even number of digits. So, we print 2.

Array = {1 , 111 , 11111 , 12345}
0

Explanation: There is no integer with an even number of digits in the given array.

Approach

The core of this problem is to count the number of digits in an integer. If we can do that, then we can repeat the process for every integer in the array and count the number of integers having an even number of digits. In binary representations, we can right shift a given integer(or divide it by 2) until it becomes zero to count the number of bits in it. Similarly, for counting digits, we can keep dividing an integer by 10 unless it becomes 0. This method is true for any base.

Find Numbers with Even Number of Digits Leetcode Solution

 

Algorithm

  1. We create a function findNumbers() to find the count of integers having an even number of digits in any array passed to it
  2. Also, we create a helper function numberOfDigits() to return the number of digits in an integer passed to it as:
    1. initialize cnt = 0
    2. while the integer, n is greater than 0:
      1. increment cnt, cnt++
      2. divide n by 10, n /= 10
    3. return cnt
  3. Initialize result = 0 to store the count of integers having an even number of digits
  4. For every element in the array:
    1. we retrieve the count of digits in it using numberOfDigits() function
    2. If the number of digits obtained is even:
      1. Increment result, result++
  5. Return result

Implementation of Find Numbers with Even Number of Digits Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

int numberOfDigits(int n)
{
    int cnt = 0;
    while(n > 0)
    {
        n /= 10;
        cnt++;
    }
    return cnt;
}

int findNumbers(vector <int> &a)
{
    int result = 0;
    for(int &i : a)
        if(numberOfDigits(i) % 2 == 0)
            result++;

    return result;
}

int main()
{
    vector <int> a = {123 , 34 , 3434 , 121 , 100};
    cout << findNumbers(a) << '\n';
    return 0;
}

Java Program

class find_numbers
{
    public static void main(String args[])
    {
        int[] a = {123 , 34 , 3434 , 121 , 100};
        System.out.println(findNumbers(a));
    }

    static int numberOfDigits(int n)
    {
        int cnt = 0;
        while(n > 0)
        {
            n /= 10;
            cnt++;
        }
        return cnt;
    }

    static int findNumbers(int[] a)
    {
        int result = 0;
        for(int i = 0 ; i < a.length ; i++)
            if(numberOfDigits(a[i]) % 2 == 0)
                result++;

        return result;
    }
}

2

Complexity Analysis of Find Numbers with Even Number of Digits Leetcode Solution

Time Complexity

The time complexity is O(N) where N = size of the array as we do a single pass of the array and the number of digits is retrieved in constant time.

Space Complexity

O(1) as we use only constant memory space.

Translate »