Encountered this program on hackerrank it was showing runtime error.
The relevant code block is shown below.
On simple array its working, but on lists its not working. Lists are only accepted.
Question statement on hackerrank:
You are given a read-only array of N integers with values also in the range [1,N] both inclusive. Each integer appears exactly once except A which appears twice and B which is missing. The task is to find the repeating and missing numbers A and B where A repeats twice and B is missing.
Input Format
First line is the length of the array – n Second line contains n integer that is elements of the array
Constraints
1 <= n <= 105 1 <= arr[i] <= n
Output Format
Print array of integers containing repeating and missing number respectively
Sample Input 0
3 3 1 3 Sample Output 0
3 2 Explanation 0
A = 3 , B = 2 Since 3 is appearing twice and 2 is missing
public static List<Integer> find_missing(List<Integer> arr) { int i; // Repeating number for (i = 0; i < arr.size(); i++) { int abs_val = Math.abs(arr.get(i)); if (arr.get(abs_val - 1) > 0) arr.get(abs_val - 1) = -arr.get(abs_val - 1); else return abs_val; } //Missing number for (i = 0; i < arr.size(); i++) { if (arr.get(i) > 0) return (i + 1); } }
Advertisement
Answer
first of all arr.get(abs_val - 1) = -arr.get(abs_val - 1);
is wrong because it’s the same as saying 5 = -3 , as lValue is indeed a value not a variable , use arr.set(index, value);
instead .
also in your code , you are using Math.abs()
which isn’y necessary because in the question , it’s said :
1 <= n <= 105 1 <= arr[i] <= n
so the values of arr[i] will always be positive.
so I edited the whole code of yours as it has many logic problems,
so for finding repeated numbers , what I do is to loop over the list , get every element then see if there is any other similar elements in the same array.
for finding repeated number , I loop over the numbers from 1 to N where N is entered by the user as specified by the problem above and check if every number is there in the list or not.
edited version of the code :
package com.example; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { List<Integer> example = new ArrayList<>(); Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); for (int i = 0; i < n; i++) { example.add(scanner.nextInt()); } List<Integer> result = find_missing(example, n); for (Integer i : result) System.out.print(i + " "); } public static List<Integer> find_missing(List<Integer> arr, int n) { List<Integer> temp = new ArrayList<>(); int i; // Repeating number for (i = 0; i < arr.size(); i++) { for (int j = i + 1; j < arr.size(); j++) { if (arr.get(j).equals(arr.get(i))){ if (temp.contains(arr.get(j))) break; temp.add(arr.get(i)); break; } } } //Missing number for (i = 1; i <= n; i++) { if (!arr.contains(i)) temp.add(i); } return temp; } }
and here is some examples of the output test cases: