top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Given a sorted array, and given a number n, find number of times n occurs in the array using C in best possible way?

+2 votes
539 views
Given a sorted array, and given a number n, find number of times n occurs in the array using C in best possible way?
posted Nov 11, 2016 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

+1 vote

I can share logic which will optimize little bit to solve this problem,

Let me divide the problem in 2 parts.

Considering Total number of elements in array is N, and key element searching is NUM, suppose it exists k times in the array.

1> Search the number and it's position in a SORTED ARRAY.
2> And getting the count of number of times the number exists.

Part 1: - Apply binary search on it and get the index where it is the number exist for this complexity will be log(N)
Part 2:- Then after getting the index where the number present,
Browse its left side till you get the same number
Browse its right side till you get the same number

So complexity K + log(N) in best/average cases , in worst case K count can be N also for all the array element is same and equal to the number you are searching for.

Example
0 1 2 3 4 5 6 7 8 9 10 (Index)
3 3 4 8 8 8 8 12 14 18 45
N = 11
Key = 8 i am searching for it
K = 4 as 8 is present 4 times.
Part 1 : Using binary search we can find that 8 is present at Index 5

Part 2:
Then go linearly towards Left side of index 5, till you get different number so here count will be 2
Then go linearly towards Right side of index 5, till you get different number so here count will be 1

So total count = 1+ 2 +1 = 4

Hope it is clear.

answer Nov 15, 2016 by Sachidananda Sahu
nice approach
0 votes
#include<stdio.h>
main()
{
        int array[10],i,num,count=0;
        for(i=0;i<10;i++)
        {
                printf("\nEnter array[%d] = ",i);
                scanf("%d",&array[i]);
        }
        printf("Enter number to find occurance\n");
        scanf("%d",&num);
        for(i=0;i<10;i++)
        {
                if(array[i]==num)
                        count++;
        }
        if(count==0)
                printf("%d is not found\n",num);
        else
                printf("%d is found %d times\n",num,count);
answer Nov 11, 2016 by Chirag Gangdev
Similar Questions
0 votes

Given an unordered array A of size n and integer x. What is the best complexity to find two elements in A whose sum is x?
Share the algo, its complexity and if possible C code.

0 votes

Given an array of sorted integers and find the closest value to the given number. Array may contain duplicate values and negative numbers.

Example : Array : 2,5,6,7,8,8,9
Target number : 5
Output : 5

Target number : 11
Output : 9

Target Number : 4
Output : 5

+4 votes

Design an algorithm to accept a string from the user. Count and print the number of times each character occurs in the given string. Example –
input string = "malayalam"
Output must be –
m – 2
a – 4
l – 2
y - 1

...