You are given an array of N integers from 1 to N. There is one integer which is repeated twice and one which is missing. Write an algorithm to find the missing integer
RE: You are given an array of N integers from 1 to N. ...
You can use the Sn n/2(n+1) to figure out the summation of 1 2 .... n numbers and using a for loop add the values of the given array. and difference between these two gives the result desired. Sometimes you want to take the absolute value of this difference.
RE: You are given an array of N integers from 1 to N. ...
we can try this:
1. Take a newarray of size N. Initialize every element of this array to 0. 2. for(i 1; i < N; i++) { newarray[i] newarray[i] + 1; } 3. find j in newarray such that newarray[j] > 1. Find k in newarray such that newarray[k] 0. 4. j is the element which is repeated twice & k is the element which is missing.
RE: You are given an array of N integers from 1 to N. ...
This Code as worked.Insteadof giving specific numbers u can give N natural numbers as inputs as specified in the question u can use the same concept of for loop .U will the result
Module Module1
sub Main()
Dim arr() as Integer {1 2 3 4 6 6 8}
for i as integer 1 to 8
if arr(i) arr(i+1) then
console.writeline( Missing number is &(arr(i+1)+1))
RE: You are given an array of N integers from 1 to N. ...
How about 5. The program doesnt print for 5. Check for difference between a[i+1] -a[i] if it is 1 the number is present. If it is 0 or 2 then a[i] +1 is missing. cases: 1 2 3 4 5 5 7 a[i+1] - a[i] 0 at i 5 so 6 is missing 1 2 3 4 6 6 7 a[i+1] -a[i] 2 at i 4 so 5 is missing.
RE: You are given an array of N integers from 1 to N. ...
As the problem himself states that an array is having integers from 1 to N so in case the array is a sorted array then simple we can find the duplicate and Missing number by
using For loop
for(i 0;i{ if( a[i] ! (i+1))
{ print( the Missing number is d and duplicate number is d (i+1) a[i]); break; }
RE: You are given an array of N integers from 1 to N. ...
Method 1: (works for any array of integer not necessarily for 1-N) 1. Sort the array using counting sort which takes O(N). 2. A for look to search the missing one and the repeated one which also takes O(N) int cur 0; for( int i 0; i<N; ++i ) { if( inputArray[i] > ++cur ) ;// find the missing one else if( inputArray[i] < ++cur) ;// find the repeated one }
Method 2: (consider the given array element is from 1 to N) 1. Define an integer array occurNum[N] with intialize value 0s; 2. A for loop to find out how many times each number occurs in the given array for( int i 0; i<N; ++i ) { occurNum[inputArray[i]-1] + 1; } 3. given a i if occurNum[i] 0 then i+1 is the missing number. if it is 2 then i+1 is the repeated one.
RE: You are given an array of N integers from 1 to N. ...
Here is the working code for finding the duplicate number with no extra array. The worst running time is 2N. The aveage time would be smaller.
// return the repeated number int findDup( int* data int N int* timeCounter ) { *timeCounter 0; bool done false; int i 0; while( i<N && !done ){ ++(*timeCounter); while( i ! data[i]-1 ){ if( data[data[i]-1] data[i] ){ done true; break; }else{ // swap the data[i] and data[data[i]-1] int temp data[data[i]-1]; data[data[i]-1] data[i]; data[i] temp; ++(*timeCounter); } } } return data[i]; }
Notice that every swaping inside the while loop puts one element back to its right spot. The total maximal number of swapping operations is N. Precisely it is N-1. The for loop is O(N). So the total performance is O(N).
