Using Loop Iteration Only (without recursion) | C++ | Page 1

scarlet pike Apr 27, 2024, 5:57 PM

#

do you have to output just the integer OR also the steps with the integer?

#

if just integer, you can just output the middle number

#

ahh okay hold on

#

I am gonna write it for you

#

@ashen roost

#

I think i got it

#

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> numbers;
    numbers.reserve(n);
    for(int i = 0; i < n; i++){
        int t;
        cin >> t;
        numbers.push_back(t);
    }
    bool isleft = 1;
    for(;;){
        if(numbers.size() == 1)
            break;
        vector<int> temparr;
        if(isleft){
            for(int i = 1; i < numbers.size(); i += 2)
                temparr.push_back(numbers[i]);
            isleft = 0;
        }
        else{
            for(int i = (numbers.size() & 1); i < numbers.size(); i += 2)
                temparr.push_back(numbers[i]);
            isleft = 1;
        }
        for(int i = 0; i < temparr.size(); i++)
            cout << temparr[i] << " ";
        cout << endl;
        numbers = temparr;
    }
    cout << numbers[0] << endl;
}

#

its gonna be really easy to write it in c

#

#include "stdio.h"

int main(){
    int n;
    scanf("%d", &n);
    int numbers[n];
    for(int i = 0; i < n; i++)
        scanf("%d", &numbers[i]);
    bool isleft = 1;
    for(;; n >>= 1){
        if(n == 1)
            break;
        int temparr[(n >> 1)];
        if(isleft){
            for(int i = 1, windex = 0; i < n; i += 2, windex++)
                temparr[windex] = numbers[i];
            isleft = 0;
        }
        else{
            for(int i = (n & 1), windex = 0; i < n; i += 2, windex++)
                temparr[windex] = numbers[i];
            isleft = 1;
        }
        for(int i = 0; i < (n >> 1); i++){
            numbers[i] = temparr[i];
            printf("%d ", temparr[i]);
        }
        printf("\n");
    }
    printf("%d \n", numbers[0]);
}

@ashen roost

#

this should work in c

#

you always begin to write into your new array from beginning of your old array to keep element order

#

every time you do iteration your size will be half of your previous size

#

if it is odd then it will be half - 0.5

#

you can use left bitshift to speed up that operation

#

when you do your scan from left to right then you start from your second element and write it into your new array

#

you keep going until you reach the end of your array, while adding 2 to your pointer

#

then you set your bool variable to 0 to indicate that you gonna go from right corner next time

#

then you start from yoursize & 1 to include odd size option

#

and do the same

#

if your size == 1 then you break out

#

no problem

#

dont cheat on your tasks tho

slim meteorBOT Apr 27, 2024, 6:17 PM

#

@scarlet pike has reached level 9. GG!

scarlet pike Apr 27, 2024, 6:18 PM

#

i swear there is gotta be some o(1) algorithm to find out that number

slim meteorBOT Apr 27, 2024, 6:18 PM

#

@ashen roost has reached level 6. GG!

scarlet pike Apr 27, 2024, 6:19 PM

#

wait it is just the element of size - 3 for odd size and size - 2 for even

#

it is overcomplicated

#

#include "stdio.h"

int main(){
    int n;
    scanf("%d", &n);
    int numbers[n];
    for(int i = 0; i < n; i++)
        scanf("%d", &numbers[i]);
    if(n < 4){
        if(n == 1)
          printf("%d \n", numbers[0]);
        else
          printf("%d \n", numbers[1]);
        return 0;
    }
    if(n & 1)
        printf("%d \n", numbers[n - 4]);
    else
        printf("%d \n", numbers[n - 3]);
}

#

here is algorithm to find the output value

#

okay

#

then (n >> 1) = n / 2

scarlet pike Apr 27, 2024, 6:25 PM

#

scarlet pike ```c #include "stdio.h" int main(){ int n; scanf("%d", &n); int num...

i have updated the program

#

i think you should try to use my code for your program and try to understand how it works, because it will perform better that your code, also, it works

#

your new size is old size / 2

#

and you have to check if your old size == 1 then you break

#

also count % 2 wont work for arrays with even element count

#

you have to define a boolean variable which will define how you go through your array

scarlet pike Apr 27, 2024, 6:30 PM

#

scarlet pike ```c #include "stdio.h" int main(){ int n; scanf("%d", &n); int num...

but if you have to just output the result then you can use this program because if the size is > 3 then the desired element is always gonna be size - 3 for even array size and size - 4 for odd array size

lunar owl Apr 27, 2024, 7:17 PM

#

scarlet pike then (n >> 1) = n / 2

thats also an bitwise operator, isnt it? :]

scarlet pike Apr 27, 2024, 7:17 PM

#

lunar owl thats also an bitwise operator, isnt it? :]

n / 2 nope

#

you read it as code

#

i meant that (n >> 1) is equal to n / 2

lunar owl Apr 27, 2024, 7:17 PM

#

oh didnt see the =

#

thought you told him to use >> 🙂

scarlet pike Apr 27, 2024, 7:18 PM

#

i mean for c programming >> is more convenient but since he said he hasnt learned bitwise operations yet i suggested n / 2

#

you start from end of the array in your second case

#

it will not work

#

because you have to keep elements order

#

so you start from (size & 1)

#

(size % 2) i suppose

#

why... do you have 2 checks for your size

#

yeah still the same issue

scarlet pike Apr 27, 2024, 7:22 PM

#

scarlet pike so you start from (size & 1)

here

scarlet pike Apr 27, 2024, 7:23 PM

#

scarlet pike you start from end of the array in your second case

and here

#

and why do you even have check for your size in your secondary loops

#

sourcesize!= 1 and sourcesize==1 in the end

#

ahh okay

#

isnt printfinalres the same as print array[0]?

#

and you can definitely do it outside of your array

scarlet pike Apr 27, 2024, 7:26 PM

#

scarlet pike and you can definitely do it outside of your array

so it wont check for it every iteration

scarlet pike Apr 27, 2024, 7:26 PM

#

scarlet pike ```c #include "stdio.h" int main(){ int n; scanf("%d", &n); int num...

like i did in my code

#

it is really clear and easy to understand

#

try to rewrite your code using mine as a referrence

#

more checks != better

#

why cant you just copy your newarray to your old array

#

you still do it

#

its just very inefficient

#

yes you have to iterate from the beginning in your second case

#

as i did in my implementation

#

you may as well copy my code to your ide and try to analyze how it works, maybe add some print things to better understand it

#

you're welcome

#

my code?

#

what doesnt work

#

to input numbers

#

ahh okay

#

heh

#

wow

#

you could have actually looked into it and had found all of your mistakes

#

it is the same as -= or += or /= or *=

#

n >>= 1

=

n = (n >> 1)

#

n % 2

#

least significant bit

#

idk just some placeholder

#

you can name it as j

#

or give it any other name you like

#

I also wonder what was the original word I came up with

scarlet pike Apr 27, 2024, 8:45 PM

#

because you dont enter them?

slim meteorBOT Apr 27, 2024, 8:45 PM

#

@ashen roost has reached level 7. GG!

scarlet pike Apr 27, 2024, 8:45 PM

#

why wouldnt you just use
scanf("%d", &matrix[i][j]);

#

yes its because scanf doesnt return anything

low quest Apr 27, 2024, 9:12 PM

#

scarlet pike here is algorithm to find the output value

It only works for n < 12

scarlet pike Apr 27, 2024, 9:12 PM

#

low quest It only works for n < 12

ahh anyway

#

i think he had to display intermediate steps so it would have not worked

low quest Apr 28, 2024, 1:17 AM

#

Here's the "constant" formula:

constexpr int getLastOneStanding(const unsigned n)
{
  const unsigned w = std::bit_width(n);
  const unsigned mask_full = ((1 << w - w % 2) - 1) * 2 / 3;
  const unsigned mask_odd = w % 2 ? mask_full : mask_full / 4;

  return (mask_full & n) + mask_odd - mask_full / 2 + 1;
}

https://godbolt.org/z/57r7WdrqP

lunar owl Apr 28, 2024, 1:30 PM

#

low quest Here's the "constant" formula: ```cpp constexpr int getLastOneStanding(const uns...

wait, thats super weird

#

i thought constexpr is used when the value is already known at compile time

#

didnt know that you can use that for a function that takes parameter

low quest Apr 28, 2024, 8:38 PM

#

Yes! constexpr means that if you call the function with an argument known at the compile time, the result of the function will also be computed at the compile time. While if you call it with a runtime argument, the result will be known at runtime. So you can write both:

std::array<int, getLastOneStanding(42)> myArray;
static_assert(getLastOneStanding(42) == 32);

And:

std::cin >> n;
std::cout << getLastOneStanding(n);

#

And the compiler will actually take advantage of that. For example, if you compile the following:

#include <bit>

constexpr int getLastOneStanding(const unsigned n)
{
  const unsigned w = std::bit_width(n);
  const unsigned mask_full = ((1 << w - w % 2) - 1) * 2 / 3;
  const unsigned mask_odd = w % 2 ? mask_full : mask_full / 4;

  return (mask_full & n) + mask_odd - mask_full / 2 + 1;
}

constexpr int getProduct(const unsigned n)
{
  int product = 1;
  for (unsigned i = 1; i < n; i++)
     product = product * getLastOneStanding(i) % 13;
  return product;
}

int main()
{
  return getProduct(100);
}

The actual assembly code (with -O1) is:

main:
        mov     eax, 4
        ret

#

Since C++20, you can also use consteval instead, which means that the function must be evaluated at the compile time (cannot be called with a runtime argument).

tender frigate Apr 28, 2024, 10:11 PM

#

lunar owl didnt know that you can use that for a function that takes parameter

contexpr can do a lot of stuff as of C++20

#Using Loop Iteration Only (without recursion)