+ 1

[SOLVED] How to find duplicates of a 2D Array?

Hii! I love asking questions here because I always learn so much from you all. So, here's me bothering with another question that has been bothering me for some days. I am trying to write a function that returns true if the numbers 1 through 9 appear exactly once each in my array, and false otherwise but I am confused as to why my code is not working the way it's supposed to in the sense that it outputs the return statement depending on if found or not. How would I do this? I am told this is supposed to be an easy problem, but I can't solve it. code: https://code.sololearn.com/c5thyz5b2Q71

10th Feb 2022, 10:19 PM
Annei ❤️
Annei ❤️ - avatar
14 Answers
+ 3
Annei ❤️ , I see. Well, it is not that I used a third-party library, but only what the language comes equipped with :) But, I am sure you have your reasons. Additionally, one can do away with the array and use a bit mask. It is the same idea, only we flip a bit at position numbers[row][column] on and see if in the end we have a certain bit pattern. const int mask = 0b1111111110; This is the desired pattern of nine bits set at the positions 1 to 9. Let's collect bits from the array: int bits = 0; for(int row ...) for(int col ...) bits |= (1 << numbers[row][col]); return ! (bool) (bits ^ mask); There is some bitwise arithmetic going on, OR ( | ) to set a bit and XOR ( ^ ) to clear all bits in the mask that are set in the bits variable. If the result is zero, all bits are cleared and thus all numbers appeared.
11th Feb 2022, 5:39 AM
Ani Jona 🕊
Ani Jona 🕊 - avatar
+ 3
Lets think of the "dumbest" solution: bool seen1 = false, seen2 = false, ... for(...) { for(...) { int current = numbers[row][column]; if (current == 1) seen1 = true; if (current == 2) seen2 = true; ... } } return seen1 && seen2 && seen3 && ...; This works because if you've seen 9 different numbers, you know they each occurred just once--there's only space for 9 elements in your array after all. (the "pigeonhole principle".) How do you tidy this up? Well, you could use an std::map, or an array of size 9, that stores how often you've seen each of the numbers. int counting_array[9] {0}; for(...) for(...) { int current = numbers[row][column] - 1; // -1, to turn the 1-9 range into 0-8. if (current < 0 || current > 8) return false; counting_array[current]++; } } And then you check whether counting_array contains a 1 everywhere. But this is just Ani Jona 🕊 's solution so there you go. :)
11th Feb 2022, 1:57 AM
Schindlabua
Schindlabua - avatar
+ 2
Your function make_array returns 0. Hence, while(make_array()) evaluates to false and the subsequent for loops are never executed. I am not sure why the call to make_array is in place of a while condition 🤔 And idea for verification: (removed because faulty)
10th Feb 2022, 11:16 PM
Ani Jona 🕊
Ani Jona 🕊 - avatar
+ 2
No, sorry, that was a mistake. Two options come to mind. First, if it is required that all numbers appear once, then you can make sure of that at the time you create the array. Just create an array with numbers 1 to 9 and use the shuffle function to create a permutation and then use it to fill the 2D array. If it is not necessary that all numbers appear and it is just out of curiosity, then you can reverse the idea. Create a 1D array of size 9, init to zero, and use the numbers in the 2D array as index (+ 1). Set the corresponding array entry to 1 and check that all are one in the end.
10th Feb 2022, 11:49 PM
Ani Jona 🕊
Ani Jona 🕊 - avatar
+ 2
Like this: #include <algorithm> bool appears_once() { int arr[9] {0}; for ( int copy_row = 0; copy_row < 3; copy_row++ ) { for ( int copy_column = 0; copy_column < 3; copy_column++ ) { arr[numbers[copy_row][copy_column] - 1] = 1; } } return all_of( cbegin(arr), cend(arr), [](int n){ return n == 1; } ); }
11th Feb 2022, 12:06 AM
Ani Jona 🕊
Ani Jona 🕊 - avatar
+ 2
(To be clear, you could make this an array of bools in my second example, but I ran out of space to elaborate further...)
11th Feb 2022, 2:00 AM
Schindlabua
Schindlabua - avatar
+ 2
This was the first idea I had but retracted in the end because it is false. The elements in the array are not unique. While it is true that if the numbers do not add up to 45 the elements are not unique. The converse, however, is false. E.g. {{2,2,3},{4,5,6},{7,8,8}} also sums up to 45, as do many other combinations.
12th Feb 2022, 12:52 PM
Ani Jona 🕊
Ani Jona 🕊 - avatar
+ 1
Wow thank you for responding! I changed the make array function to a void, but wanted to use the array in that function in the bool but did not know how to use it so I used the while 😅 I am confusing myself - but I also do not get the last part. I want to know if they appear more than once.. will this verification still help?
10th Feb 2022, 11:21 PM
Annei ❤️
Annei ❤️ - avatar
+ 1
Thank you!! Though, I’ve solved it already ❤️
11th Feb 2022, 5:44 AM
Annei ❤️
Annei ❤️ - avatar
+ 1
Ah, very good :)
11th Feb 2022, 5:50 AM
Ani Jona 🕊
Ani Jona 🕊 - avatar
0
Ok, but how do I use the nunbers in the 2d array in this new array?
10th Feb 2022, 11:54 PM
Annei ❤️
Annei ❤️ - avatar
0
Thank tout!! but I am attempting to not use any additional libraries..
11th Feb 2022, 12:09 AM
Annei ❤️
Annei ❤️ - avatar
0
For a 3x3 array, the sum of all its members, if they are unique and do not include 0, will be equal to 45. You can simply subtract from 45 the sum of all array members and if they are not unique, the result will not equal 0. https://code.sololearn.com/cizuMMtFiiwT/?ref=app Java code for example.
12th Feb 2022, 12:40 PM
Alex
0
Alex You are thinking of the problem where you have a list of numbers but one is missing and you have to figure out which one it is. But that doesn't work here.
12th Feb 2022, 12:56 PM
Schindlabua
Schindlabua - avatar