Find all array elements occurring more than ⌊N/3⌋ times.

 Q. Find all array elements occurring more than ⌊N/3⌋ times.


Solution in java :

  // find elements in the array that occurs more than n/3 times in array
  // 19 march 2021 
  // T.U.F Question 
  import java.util.*;
  class cf
  {
    static void calc(int[] arr ) {
      int len = arr.length;

  //first solution 
      // HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
      // for(int i=0;i<len;i++) {
      //   if(!map.containsKey(arr[i])){
      //     map.put(arr[i],1);
      //   }
      //   else{
      //       map.put(arr[i],map.get(arr[i])+1);
      //   }
      // }
      // System.out.println(map);
      // map.forEach((key,value)-> {
      //   if(value>len/3)
      //   System.out.println(key);
      // });

      int cnt1 = 0;
      int cnt2 = 0;
      int num1 = -1;
      int num2 = -1;

      for(int i=0;i<len;i++) {
        if(arr[i] == num1){
          cnt1++;
        }
        else if(arr[i] == num2){
          cnt2++;
        }
        else if(cnt1 == 0){
          num1 = arr[i];
        }
        else if(cnt2 == 0){
          num2 = arr[i];
        }
        else {
          cnt1--;
          cnt2--;
        }
      }
      System.out.println(num1);
      System.out.println(num2);
      //also check the frequency of num1 and num2 in array. Not always the answer will be correct.
      // if freq(num1 or num2) < n/3 dont print it 
      // I am not implementing that code to check frequency.
    }
    static Scanner input = new Scanner(System.in);
    public static void main(String[] args) {
      try
      { 
        int arr[] = {1,1,1,1,1,2,2,2,3,3,3,3};
        calc(arr);
      }
      catch(Exception e){
        return;
      }
    }
  }

Output :

  Input: arr[] = {5, 3, 5}
  Output: 5
  Explanation:
  The frequency of 5 is 2, which is more than N/3( = 3/3 = 1).

  Input: arr[] = {7, 7, 7, 3, 4, 4, 4, 5}
  Output: 4 7
  Explanation:
  The frequency of 7 and 4 in the array is 3, which is more than N/3( = 8/3 = 2).

Popular Posts

Family Tree Project in Java

Image
Creating Family tree in java .  Trees are such an important structure in computer science. But what more important tree, than our family tree? ❤️   👨‍👩‍👧‍👦   ❤️    Made this simple program in java to implement family tree. Java File import java.util.*; class Person { String name; boolean married; String wife; int noOfChild; Person[] childs; public Person(String name){ this.name = name; } public Person(String name,boolean married,String wife,Person[] childs,int noOfChild) { this.name = name; this.married = married; this.wife = wife; this.childs = childs; this.noOfChild = noOfChild; } public Person(String name , boolean married,String wife) { this.name = name; this.married = married; this.wife = wife; } } class familyTree { static int population; static Scanner input = new Scanner...
View post ��

java:17: error: local variables referenced from a lambda expression must be final or effectively final count ++ ;

Image
 Modifying variables inside java lambdas. Integer list[] = {1,2,3,4,5,6,7,8}; int index = 0; Arrays.asList(list).forEach(e -> { System.out.println(e+" at index "+index); index++; }); Error : maze2.java:22: error: local variables referenced from a lambda expression must be final or effectively final System.out.println(e+" at index "+index); ^ maze2.java:23: error: local variables referenced from a lambda expression must be final or effectively final index++; ^ Solution : Integer list[] = {1,2,3,4,5,6,7,8}; int[] index = {0}; Arrays.asList(list).forEach(e -> { System.out.println(e+" at index "+index[0]); index[0]++; }); Output : 1 at index 0 2 at index 1 3 at index 2 4 at index 3 5 at index 4 6 at index 5 7 at index 6 8 at index 7
View post ��

Creating basic tic tac toe android app using java

Image
 Marvel Tic Tac Toe Android Game ( Java ) In this blog I we will create basic android app. We will be coding in java.   package com.example.batvsiron ; import androidx.appcompat.app.AppCompatActivity ; import android.os.Bundle ; import android.util.Log ; import android.view.View ; import android.widget.Button ; import android.widget.GridLayout ; import android.widget.ImageView ; import android.widget.TextView ; import android.widget.Toast ; import java.util.Arrays ; public class MainActivity extends AppCompatActivity { int active = 0 ; public int [][] winningPosition = { { 0 , 1 , 2 } , { 3 , 4 , 5 } , { 6 , 7 , 8 } , { 0 , 3 , 6 } , { 1 , 4 , 7 } , { 2 , 5 , 8 } , { 0 , 4 , 8 } , { 2 , 4 , 6 } } ; public int [] moves = { 111 , 111 , 111 , 111 , 111 , 111 , 111 , 111 , 111 } ; public int checkWinning () { for ( int [] arr : winningPosition ) { ...
View post ��