Search insert position of K in a sorted array Geeks For Geeks

-

 Problem Link:


(It is also the problem of the day for 23-04-2022)


Solution:


class Solution

{

    static int searchInsertK(int arr[], int n, int k)

    {

        boolean flag=true;

        int pos=0;

        for(int i=0;i<n;i++){

            if(arr[i]==k){

                flag=false;

                pos=i;

            }

        }

        if(flag==true){

            for(int i=0;i<arr.length-1;i++){

                if(arr[i]<k && k<arr[i+1]){

                    pos=i+1;

                    break;

                }

                else if(k>arr[arr.length-1]){

                    pos=arr.length;

                }

                else if(k<arr[0]){

                    pos=0;

                }

            }

            return pos;

        }

        else{

            return pos;

        }

        

    }

}



Total Test Cases:304

Time Complexity:   O(N)[GFG Time:0.44/3.09][Linear Search]

Space Complexity: O(N)[Array is given.]

Auxiliary Space: O(1)

Approach Used:

Here first of all we will traverse the array and if we found an element then we will return its index, or if not then we will traverse the array another time and check for 3 cases:

1. if the element to be searched has a value within the array means it is greater than some element in the array and smaller than the next element in the array then return index+1

2. if its value is smaller than the 0th element of the array then return 0

3. If its value is more than the last element of the array then return arr. length


boolean flag=true is used to check the status of an element's presence in the array.

While the first iteration, if an element is present in the array flag, will change and become false, otherwise it will remain true.



"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"

Comments

Post a Comment

Popular posts from this blog

Solutions Of Practice Questions Dated 01-06-2022

-
Question 1: Transmit the Message: Solution: import java.util.*; class Solution{     public static void main(String arg[]){         Scanner sc=new Scanner(System.in);         String s=sc.next();                          ArrayList<Integer>aa=new ArrayList<Integer>();         ArrayList<Character>ab=new ArrayList<Character>();                  char flag=s.charAt(0);        int index=0;        int count=1;         for(int i=1;i<s.length();i++){             if(flag==s.charAt(i)){                 count++;             }             else{                 aa.add(index,count);                 ab.add(index,flag);                 count=1;                 flag=s.charAt(i);                 index++;             }         }         aa.add(index,count);         ab.add(index,flag);                  int max=Collections.max(aa);                  for(int i=aa.size()-1;i>0;i--){             if(aa.get(i)==max){                 flag=ab.get(i);                 break;             }
Read more

CODEFORCES SPY DETECTED ROUND 713

-
 import java.util.*; public class CodeForcesSpyDetected{ public static void main(String arg[]){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); ArrayList <Integer> aa=new ArrayList<Integer>();  while(t -->0){ int n=sc.nextInt(); int arr2[]=new int[n]; for(int i=0;i<n;i++){ arr2[i]=sc.nextInt(); } for(int i=0;i<n;i++){ aa.add(arr2[i]); } for(int i=0;i<aa.size();i++){ //System.out.println(Collections.frequency(aa,aa.get(i))); if(Collections.frequency(aa,aa.get(i))==1){ System.out.println((i+1)); aa.clear(); break; } } } } }
Read more

Maximum Winning Score Geeks For Geeks

-
Problem Link: https://practice.geeksforgeeks.org/problems/4ead9c3991a3822f578309e2232bc5415ac35cb9/1# It is also the problem of the day for 5 march. Solution: class Solution {     public static Long findMaxScore(Node root)     {         Node temp=root;         long sum=0;         while(temp!=null){             if(temp.right==null && temp.left==null){                 return (long) temp.data;             }             else{                 return (long) temp.data*Long.max(findMaxScore(temp.left),findMaxScore(temp.right));             }         }         return sum;     } } Time Complexity:[GFG Time:0.7/2.9] Space Complexity: O(N)[Number of nodes given in tree] Auxiliary Space: O(1) Approach Used: Here we used an approach that we will traverse recursively. And when we travel recursive we follow the bottom to the top approach of the tree.  It means we will see the leaf node and then move up to the tree.  For recursion, we should have a base condition and that is when node. right or
Read more