0

I was looking over some basic questions that might be asked in an interview. Using basic for loops (No hash maps etc)I want to sum up all the matching elements in an array.For example, 6 matching elements will result in (Matched: 6) and a total of 36 in the example below.An example of this could be rolling dice, and the score is the total of all the dice that match.

public static void main(String[] args) { int arr[] = {6,6,6,6,6,6}; int matched = 1; int value = 0; int total = 0; for(int i=0;i<arr.length;i++){ for(int j=(i+1);j<arr.length;j++){ if(ar[i] == ar[j]){ matched++; value = ar[i]; break; } } total = (matched * value); } // End for loop System.out.println("Matched:"+(matched)+""); System.out.println("Total:"+total); }

But, if the array was for example...

int arr[] = {6,1,1,6,6,6};

The output I get will be (Matched:5) and an a total of 30.Can could I store the matching pair of 1's and add them to the total using as little basic code as possible?

Improve this question
9
  • What output do you actually want here? Just summing all the elements is trivial, so I assume you want something else. Commented Dec 8, 2017 at 8:47
  • Requirements are unclear. How does {6,1,1,6,6,6} result in (Matched:5) and an a total of 30? Commented Dec 8, 2017 at 8:47
  • cough cough hash table cough cough Commented Dec 8, 2017 at 8:50
  • 1
    But if it matches "4 six's" shouldn't it also match "2 ones" and have 6 as matched result? Commented Dec 8, 2017 at 8:54
  • 1
    @TimBiegeleisen: I might be jumping at conclusions here but i think he only wants to sum up numbers that appear at least twice. so {6,1,1,6,6,6} and {5,6,1,1,6,6,6} probably should yield the same result. Commented Dec 8, 2017 at 8:57

5 Answers 5

Reset to default
1

Interpreting the question as "provide the total number of values that occur more than once and their sum", and taking into account that nothing "fancy" (sic) such as a map can be used:

int[] array = {6, 1, 1, 6, 6, 6}; int sum = 0; int matches = 0; for (int i = 0; i < array.length; i++) { for (int j = 0; j < array.length; j++) { if (i != j && array[i] == array[j]) { sum += array[i]; matches++; break; } } } System.out.println(matches); // 6 System.out.println(sum); // 26
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

If you are allowed to use arrays - if not too fancy - then you could use 3 loops:

  1. The first finds minimum and maximum elements
  2. The second determines the occurrence of each item
  3. The third calculates the totals

In Java this would look like this:

public static void main(String[] args) { int[] array = {6, 3, 3, 6, 6, 6, 4, 4, 20}; int min = array[0]; int max = array[0]; // Find min max for (int i : array) { if (i < min) { min = i; } if (i > max) { max = i; } } // Use array to sum up all elements int[] holderArray = new int[max - min + 1]; for (int i : array) { holderArray[i - min]++; } // Calculate occurrence and sums for(int i = 0; i < holderArray.length; i++) { if(holderArray[i] > 0) { System.out.printf("number: %2d; count: %2d; sum: %2d%n", i + min, holderArray[i], (i + min) * holderArray[i]); } } }

This prints out:

number: 3; count: 2; sum: 6 number: 4; count: 2; sum: 8 number: 6; count: 4; sum: 24 number: 20; count: 1; sum: 20
Improve this answer

2 Comments

Good job...just the solution I was looking for.
Thank you. I was just a bit unsure if arrays were allowed.
0

I don't completely understand your question, but based from what I understood, you want to get the sum of all matched numbers if its greater than 1? In that case there is a O(n) solution that you could use.

Create an empty Map then iterate over the array, and if the current number is not within the map add it to the map with value 1, if the current element is already existing in the map then just increment it's value (val++), at the end you will have a map and for each key (each distinct number) you will have the number of matched numbers from the array as the value. All you need to do is iterate over the pairs of key,val multiply each key*val then sum up the multiplied values and you get your correct total. And if you need just the number of matched, you can in another variable sum up just the vals.

So for lets say array [1,1,5,1,5,2,2,5,1], your map will something like:

{1:4, 2:2, 5:3},

and your totals:

total matches: 9

total: 23

I hope this helps!

Improve this answer

7 Comments

My question is simply what If an interviewer asked me to sum up all of the matching elements in an integer array based on their value.Using just for loops etc...no hash maps or anything fancy.
Actually, if you start counting the matches from 0, then for the sum you will need to multiply key * (value + 1)
@BalázsKovacsics oh let me update my answer, sorry you should start populating the Map with 1 instead of 0. Nice catch!
@McLovin: And your Interviewer didn't give you a description what criteria elements must have to be "matching elements"? That's kind of an important detail.
Numbers that match with what exactly? You still haven't told us that. With other numbers in the array I would guess (aka all numbers that appear at least twice) but it would be better if you just told us instead of keeping us guessing.
|
0

Here is a code fragment I just wrote. This method takes in an array of integers and creates a map of each unique integer and it's count in the list. In the second part of the method, the HashMap object countOfNumbersMap is iterated and the sum of each element is printed. 

private void findSumOfMatchingNumbers(int array[]) { HashMap<Integer, Integer> countOfNumbersMap = new HashMap<>(); // Setting up the map of unique integers and it's count for (int i = 0 ; i < array.length ; i++) { if (countOfNumbersMap.containsKey(array[i])) { int currentCount = countOfNumbersMap.get(array[i]); countOfNumbersMap.put(array[i], currentCount + 1); } else { countOfNumbersMap.put(array[i], 1); } } for (Integer integer : countOfNumbersMap.keySet()) { int sum = countOfNumbersMap.get(integer) * integer; System.out.println(String.format("Number = %d, Sum = %d", integer, sum)); } }

The worst case runtime of the program is O(n).

Improve this answer

1 Comment

The OP said that hashMap shouldn't be used in the answer, only basic loops.
0

If the range of your integers is limited, the easiest way to do this would be to create a histogram (i.e. create an array, where under index i you store the number of occurrences of the number i). From that, it's easy to find elements that occur more than once, and sum them up. This solution has a complexity of O(n+k), where k is the range of your integers.

Another solution is to sort the array,then the matching numbers will be next to each other, and it's easy to count them. This has O(nlogn) complexity.

If these methods are not allowed, here is a solution in O(n^2) that only uses for loops:

  1. Sum up the whole array
  2. With a double loop, find all elements that are unique, subtract them from the sum, and count their number.

The remaining sum is the sum of all elements occurring more than once, and the count of unique elements subtracted from the length of the array gives the number of matching element.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.