Win a copy of Bad Programming Practices 101 (e-book) this week in the Beginning Java forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Java Puzzle

Ranch Hand
Posts: 84
HI...
Problem: If ‘n’ is the positive number and ‘a’ is an array of integers of length n-1 containing elements from 1 to n. Then find the missing number in ‘a’ in the range from 1 to n. Occurrence of each element is only once. i.e ‘a’ does not contain duplicates.

Example :
If n = 8, then array ‘a’ will have 7 elements in the range from 1 to 8. For example {1, 4, 5, 3, 7, 8, 6}. One number will be missing in ‘a’ (2 in this case). You have to find out that missing number.

Solution :
Step 1 : First we find out sum of ‘n’ numbers by using formula n*(n+1)/2.

Step 2 : Then we will find sum of all elements of array ‘a’.

Step 3 : Missing_Number = (Sum of 1 to ‘n’ numbers) – (Sum of elements of array ‘a’)

This solution is feasible for finding if any single number is missing from the array. What if multiple numbers are missing from our array. So how can we find? Thanks in advance Kindly help

Marshal
Posts: 59389
187

priyanshi bhardwaj wrote:. . . . What if multiple numbers are missing from our array. . . .

If there are no duplicates, how can there be more than one number missing?

That solution with the sum and the triangular number looks good; it will run in linear time.

priyanshi bhardwaj
Ranch Hand
Posts: 84
Ok wt if we remove this unique condition and reframe the question as
find the missing numbers within a range from 1 to n (inclusive)?

Master Rancher
Posts: 89
13

priyanshi bhardwaj wrote:Ok wt if we remove this unique condition and reframe the question as
find the missing numbers within a range from 1 to n (inclusive)?

The simple, brute force approach would be to sort the array and then count through the numbers in a for loop. If the number at the index of the counter is not the same as the counter add it to your return list.

-Zach

Master Rancher
Posts: 2696
92
A linear time solution: create an Object[] the size of n, then for every present value i put an Object in Object[i]. In the end, some Object[x] will not have a value.

priyanshi bhardwaj
Ranch Hand
Posts: 84
thanks, I did the same. I have taken an array list now the problem is only how to convert an array list to an array? please help I haven't used ArrayList before and I have to submit this code in my lab exercise tomorrow i just mean it's urgent. Thanks in advance.

priyanshi bhardwaj
Ranch Hand
Posts: 84

priyanshi bhardwaj wrote:thanks, I did the same. I have taken an array list now the problem is only how to convert an array list to an array? please help I haven't used ArrayList before and I have to submit this code in my lab exercise tomorrow, I just mean it's urgent. Thanks in advance.

I Mean the return type of my function is an array

priyanshi bhardwaj
Ranch Hand
Posts: 84

priyanshi bhardwaj wrote:

priyanshi bhardwaj wrote:thanks, I did the same. I have taken an array list now the problem is only how to convert an array list to an array? please help I haven't used ArrayList before and I have to submit this code in my lab exercise tomorrow, I just mean it's urgent. Thanks in advance.

I Mean the return type of my function is an array

I have attached the error i am facing
Absent-error.PNG

author & internet detective
Marshal
Posts: 38366
645
For the first one, .length is for an array. .size() is for an ArrayList.

For the others, you'll need to show your code.

priyanshi bhardwaj
Ranch Hand
Posts: 84

Jeanne Boyarsky wrote:For the first one, .length is for an array. .size() is for an ArrayList.

For the others, you'll need to show your code.

Sheriff
Posts: 4964
136
• 1
Here you have a raw ArrayList that you try to convert to an Integer array which you then try to convert to an int array.  Neither of those is going to work.

I would declare ms like this: ...then return ms.  But you would have to change the return type of your method and modify how the class uses the method.

Piet Souris
Master Rancher
Posts: 2696
92
• 1
The solution that I hinted to works even when there are duplicates and more than one missing. For instance:

priyanshi bhardwaj
Ranch Hand
Posts: 84
@Piet Souris Thanks your solution worked out for me. Thank you very much

 They gave me pumpkin ice cream. It was not pumpkin pie ice cream. Wiping my tongue on this tiny ad: Why should you try IntelliJ IDEA ? https://coderanch.com/wiki/696337/IntelliJ-IDEA