Tuesday, 7 October 2014

Find smallest +ve no. missing from the array

Original link:http://www.careercup.com/question?id=12708671

You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space. 
Eg: 
Input = {2, 3, 7, 6, 8, -1, -10, 15} 
Output = 1 

Input = { 2, 3, -7, 6, 8, 1, -10, 15 } 
Output = 4

Solution:
1.) Partition the array into the values smaller than zero and +ve integers using the Quicksort partition method. This can be done in O(n) time and in the same array.
2.) Now you the index of element '0' or first +ve number, say this is idxZ.
3.) Traverse starting from idxZ and set the sign bit of the value at position (idxZ + A[idxZ]) to 1. You do this only in case the value of position lies in the bounds of array.
4.) Now starting at 'idxZ' find the first position where the sign bit is UNSET. This gives you the number you are looking for.

1 comment:

  1. Hadoop concepts, Applying modelling through R programming using Machine learning algorithms and illustrate impeccable Data Visualization by leveraging on 'R' capabilities.With companies across industries striving to bring their research and analysis (R&A) departments up to speed, the demand for qualified data scientists is rising.
    data science training in bangalore
    Big Data and Hadoop training Unlike traditional systems, Big Data and Hadoop enables multiple types of analytic workloads to run on the same data, at the same time, at massive scale on industry-standard hardware.myTectra Big Data and Hadoop training is designed to help you become a expert Hadoop developer. myTectra offers Big Data Hadoop Training in Bangalore using Class Room.
    hadoop training in bangalore
    Looking for best Machine Learning Training in Bangalore then join myTectra the leader in Machine Learning Training in Bangalore. Classroom & Online Training
    machine learning training in bangalore

    ReplyDelete