• Post Reply Bookmark Topic Watch Topic
  • New Topic
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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Java Puzzle

 
Ranch Hand
Posts: 251
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 251
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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)?
 
Rancher
Posts: 89
13
Scala Eclipse IDE MySQL Database Tomcat Server Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 251
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 251
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 251
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 41860
908
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 251
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 7125
184
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Bartender
Posts: 5465
212
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 251
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Piet Souris Thanks your solution worked out for me. Thank you very much
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic