Tag: algorithm

Find Numbers with Even Number of Digits

August 14th, 2020

Given an array nums of integers, return how many of them contain an even number of digits.

Example 1:

Input: nums = [12,345,2,6,7896]
Output: 2

Example 2:

Input: nums = [555,901,482,1771]
Output: 1

Solution

Loop through Array
Find number of digits in each number
Increase counter by 1 if number of digits in the number is even

/**
 * FindNumbersWithEvenNumberOfDigits.java
 * Purpose: Find Numbers with Even Number of Digits
 *
 * @author Megha Rastogi
 * @version 1.0 08/09/2020
 */
class FindNumbersWithEvenNumberOfDigits {

    /**
     * Find Numbers with Even Number of Digits
     *
     * @param Array, nums
     * @return integer, numberOfEvenDigitNumbers
     */
    public int findNumbers(int[] nums) {
        
        // initialize the variable to store the count of
        // even digit numbers
        int numberOfEvenDigitNumbers = 0;
        
        // loop through the array and increase the counter
        // if number of digits are even
        for(int num: nums){
            if(numberOfDigits(num) % 2 == 0)
                numberOfEvenDigitNumbers++;
        }
        
        //return the result
        return numberOfEvenDigitNumbers;
    }
    
    /**
     * Find number of digits in an integer
     *
     * @param integer, num
     * @return integer, numberOfDigits
     */
    public int numberOfDigits(int num){
        
        // initialize the counter to store number of digits
        int numberOfDigits = 0;
        
        // loop until number is greater than 0
        // Continuously divide num by 10
        // increase the numberOfDigits by 1
        while(num > 0){
            num /= 10;
            numberOfDigits++;
        }
        
        // return  the result
        return numberOfDigits;
    }
}

Source – Leetcode

Code – FindNumbersWithEvenNumberOfDigits.java

Maximum Subarray

June 6th, 2020
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:
```
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
```
Solution

We need to find the maximum sum contiguous subarray here. Let’s start from the example above. Let’s keep track of sum and maxSum which is a very small number N. And start summing from the beginning –
- for -2, sum is -2, maxSum will still become -2.
- sum of -2 and 1 will be -1, A thing to note here is our new sum -1 is less than the current value 1. So our sum should become 1 and max between -2 and 1 is 1. Therefore our maxSum is also 1.
- sum of 1 and -3 is -2. maxSum between -2, 1 is 1.
- sum of -2 and 4 is 2, which is less than 4. so sum becomes 4. and maxSum becomes 4.
- And we keep doing this until we reach end.
Our basic algorithm will be
- Take two variables sum and maxSum to keep track of sum and maxSum till a given position in array.
- Loop through the array
  - sum is addition of sum and current value in the array. If sum < current value in the array, sum becomes current value in the array.
  - maxSum is maximum of maxSum and sum.
  - Repeat above steps until we reach the end of the loop.
- return the maxSum
```
/**
 * MaxSubArray.java
 * Purpose: Find maximum sum contiguous subarray 
 *
 * @author Megha Rastogi
 * @version 1.0 06/06/2020
 */
class MaxSubArray {
    
    /**
     * Find maximum sum contiguous subarray 
     *
     * @param Array, nums
     * @return integer, maxSum
     */
    public int maxSubArray(int[] nums) {
        
        // Initalize maxSum and sum
        int maxSum = Integer.MIN_VALUE, sum = 0;
        
        // Loop through the array
        for(int i = 0; i < nums.length; i++){
            
            // add current value to sum
            sum+=nums[i];
            
            // update sum if it becomes less than current value
            if(sum < nums[i])
                sum = nums[i];
            
            // update the max sum
            maxSum = Math.max(maxSum, sum);
        }
        
        //return the max sum
        return maxSum;
    }
}
```
Code – MaxSubArray.java

Source – Leetcode

Tag: algorithm

Find Numbers with Even Number of Digits

Solution

Maximum Subarray

Solution