Win a copy of Classic Computer Science Problems in Swift this week in the iOS forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Java Puzzle  RSS feed

 
Ranch Hand
Posts: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 58830
179
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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)?
 
Ranch Hand
Posts: 38
4
Eclipse IDE Java MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 2552
87
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
[Thumbnail for Absent-error.PNG]
 
author & internet detective
Marshal
Posts: 38152
617
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 4838
135
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 2552
87
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The solution that I hinted to works even when there are duplicates and more than one missing. For instance:
 
priyanshi bhardwaj
Ranch Hand
Posts: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Piet Souris Thanks your solution worked out for me. Thank you very much
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!