CODEWITHSUNDEEP
algorithm
Md Azharuddin
Md Azharuddin

Reputation: 1476

Algorithm to count maximum possible pairs

I have an array of numbers say arr=[3,4,2,3,1]. Here index of arr represents number while arr[index] represents the frequency of that number. For the example arr we have

1 three times
2 four times
3 two times
4 three times
5 one time

A pair can consist of two numbers such that their absolute difference is either 0 or 1. We need to find maximum possible pairs. A number cannot be used more than its provided frequency. For the example arr pairs can be:
(1,1),(2,2),(2,2),(3,3),(4,4),(4,5)
Thus 6 is the answer.
Note: Here we are left with an extra 1 but that doesn't matter.

My approach:
Calculate the mod 2 for each number and obtain an array of 0 and 1 and for each frequency update count by count += arr[i]/2. So for the example arr I will be left with: [1,0,0,1,1]
Now if I see any two consecutive 1 update count by 1

It worked for sample test cases but failed in hidden test cases. Can anyone help me figure out what's wrong with my idea?

Failed Case:
[34,2,435,45,57,6,8,3,57,235]
My output: 440
Expected output: 441

Upvotes: 1

Views: 403

Answers (2)

sachco
sachco

Reputation: 294

Logic behind is

take arr[i]/2 into the count and if odd is element take one as a carry for the next

      public static void main(String args[]) {
                int[] arr=new int[]{34,2,435,45,57,6,8,3,57,235};
                int len=arr.length;
                int count=0,prev=0;
                if(arr[0]%2!=0)prev=1;
                count+=arr[0]/2;
                for(int i=1;i<len;i++){
                    if(prev==1){
                       arr[i]--;
                       count++;
                    }
                    if(arr[i]%2!=0)prev=1;
                    else prev=0;
                    count+=arr[i]/2;
                    
                }
        
              System.out.println(count);
        }

Time Complexity is O(n) and space is O(1)

Upvotes: 3

MBo
MBo

Reputation: 80187

Note that with your approach you don't use the last one from 57.

But you can pair this one with one from 6, another one from 6 will be paired with 8, 8 will paired with 3, and 57 with 235 - so all items do work.

You need to choose at every step: what's better - left last one free or make a pair with the next value.

Upvotes: 1

Related Questions